Problem #1

TSOJ P1508
定义:对于整数序列A,若整数a∈A,且出现的次数最多,则称a是A的最高频率元素。
现在,给定一个包含L个整数的序列A,并且存在一个整数X,它出现的次数大于L/2,因此X是最高频率元素,且唯一。请找出元素X。

Solution #1 模拟 时间O(L), 空间O(max{A})

一维数组,整数大小作为下标,模拟计数,求最大值。

代码略

Solution #2 时间O(L), 空间 O(1)

两个整数模拟栈的操作。对于极限情况,出现次数最多的数 出现次数为floor(L/2)+1,则用floor(L/2)个不同元素消去后,栈内还存在一个数,此数即为出现次数最多的数。

Note 1: 此题(TSOJ P1508)为最简单的形式,此题还可以有更多变式。

因为用此方法时,只需比较两数是否相等,所以也可以使用字符串来进行处理。这样可以处理出现大整数的情况。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main() {
    string t, s;
    int c;
    for(int n; cin >> n;) {
        c = 0;
        s = t = "";
        for(int i = 0; i < n ; i++) {
            cin >> t;
            if(t != s) {
                if(s == "") {
                    s = t;
                    c = 1;
                } else {
                    if(c == 1) {
                        c = 0;
                        s = "";
                    } else {
                        c--;
                    }
                }
            } else {
                c++;
            }
        }
        cout << s << endl;
    }
    return 0;
}

 

Problem #2

TSOJ P1162
某火车站铁轨铺设如图,有 n 节车厢自 A 方向进入车站,按进站方向编号为 1 ~ n。现对其进行编组,编组过程可借助中转站 Station,其中 Station 可停靠任意多车厢,由于 Station 末端封顶,故驶入 Station 的车辆必须按相反方向驶出。对每个车厢,一旦自 A 进入 Station,就不能再驶入 A;且一旦自 Station 驶入 B,再不能返回 Station。给定 n 值,请判断某个车厢编组是否可能。

Solution #1 栈模拟

Solution #2 空间复杂度O(n) 时间复杂度 O(nlogn)

因为 进站可视为单调上升的栈,所以当 x 出栈时,所有比x大的已入栈元素一定已经出栈。

所以 所有比最后一个已入栈元素大的元素一定没有入栈

所以 当 子序列中的最小元素m已经出栈时,出栈序列中m左边的所有元素均比m右边的所有元素小

所以 在子序列 中,

a[i] = m, i = max{a[1..i]} (*)

可根据(*)式进行递归。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 110000;

int a[N];

bool exec(int l, int r, int m) {
    if(r - l < 2) return true;
    int v = -1;
    for(int i = l; i <= r; i++) {
        v = max(a[i], v);
        if(a[i] == m) {
            if(v - m  != i - l) {
                return false;
            } else {
                return exec(l, i - 1, m + 1) && exec(i + 1, r, v + 1);
            }
        }
    }
}

int main() {
    for(int n; cin >> n;) {
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        cout << (exec(1, n, 1) ? "Yes" : "No") << endl;
    }
    return 0;
}

 

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注