Link

点击打开uva题目链接

Mean

有n个绝对值各不相同的非0整数,选出尽量多的数,排成一个序列,使得正负号交替,且绝对值递增。n最大为500000

Analyse

按正负分在两个vector里,然后排一下序,有两种情况:正数在前和负数在前。这样分情况用双指针走一遍即可,总的时间复杂度为O(n*logn + 2*n)

C++ Code

#include <bits/stdc++.h>
using namespace std;

int calc(const vector<int> &A, const vector<int> &B) {
    int cnt = 1, cur = A.front(), i = 1, j = 0;
    while(true) {
        if(cnt % 2) {
            while(j < B.size() && B[j] < cur)
                ++j;
            if(j >= B.size()) return cnt;
            cur = B[j++];
        } else {
            while(i < A.size() && A[i] < cur)
                ++i;
            if(i >= A.size()) return cnt;
            cur = A[i++];
        }
        ++cnt;
    }
}

int main() {
    int T; scanf("%d", &T);
    vector<int> A, B;
    while(T--) {
        A.clear(), B.clear();
        int n; scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            int x; scanf("%d", &x);
            if(x > 0) A.push_back(x);
            else B.push_back(-x);
        }
        sort(A.begin(), A.end());
        sort(B.begin(), B.end());
        printf("%d\n", max(calc(A, B), calc(B, A)));

    }
    return 0;
}

欢迎留言