很不错的思维题，贪心
题目大意：给你n个数，你需要找到一个最长的子序列，使得这个子序列的第4k-4k+3项为a,b,a,b的形式(从0标号)。
牛逼的贪心啊，思维能力还是不行......
思路倒是能想一点，但是代码写下来不行...
参考了 http://www.cnblogs.com/shiina-mashiro/p/3981944.html
思路：
1、处理四个数相等的情况，直接输出四个数就行----其中记录数出现的次数用map，这样就不用离散化了（网上查的说map的查询时logn，离散化需要排序，nlogn，需要把大数映射成小数的时候 岂不是不需要离散化了。。。）
2、ABAB的情况
首先要想明白一点：两对数要满足形成ABAB那么必然是相邻的 ，最初没考虑到这点，以为要O(n^2)算法，不敢写了。
然后举出相邻两对数分析思路（a,b） (c,d)。
d>b显然，因为d是当前读到的数，a,b,c,是之前读到的数
然后根据c与a,b关系分以下情况：
(1)c (2)b>c>=a 形成ABAB，记录之
(3)c>=b 不知道(a,b) (c,d) 该取哪个 那么都存下先，等着下一个数读入作处理
//#pragma comment(linker, "/STACK:102400000,102400000")#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <iostream>#include <map>#include <vector>using namespace std;#define ls(rt) rt*2#define rs(rt) rt*2+1#define ll long long#define ull unsigned long long#define rep(i,s,e) for(int i=s;i<e repe for i="s;i<=e;i++)#define" cl memset in freopen out ll ll_inf="((ull)(-1))">>1;const double EPS = 1e-8;const int INF = 100000000;const int MAXN = 500000+100;struct Node{ int l,r; int x;}nodes[MAXN];map<int int>pos,cnt;vector<int>b;int num[MAXN],n,top;void read(){ b.clear(); top=0; for(int i=1;i0) { int bl=nodes[top-1].l, br=nodes[top-1].r, bx=nodes[top-1].x; if(l>bl && l <br> <br> <p></p> <p><br> </p> <p><br> </p> </int></int></e></vector></map></iostream></string></algorithm></cstring></cstdio>登入後複製
