题意:给定n个非0绝对值不相同的数,让他们排成一列,符号交替但绝对值递增,求最长的序列长度。
析:我个去简单啊,也就是个水题。首先先把他们的绝对值按递增的顺序排序,然后呢,挨着扫一遍,只有符号不同才计数,easy!!!
代码如下:
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; const int maxn = 500000 + 10; struct node{ int num, pnum; node(){ } node(int n) : num(n){ pnum = abs(n); } bool operator < (const node &p) const { return pnum < p.pnum; } }; node a[maxn]; int main(){ int n, x, T; cin >> T; while(T--){ scanf("%d", &n); for(int i = 0; i < n; ++i){ scanf("%d", &x); a[i] = node(x); } sort(a, a+n); int cnt = 1; int ok = a[0].num > 0 ? 1 : 0; for(int i = 1; i < n; ++i) if((a[i].num > 0 && !ok ) || (ok && a[i].num < 0)){ ++cnt; ok = !ok; } printf("%d ", cnt); } return 0; }