PHP8.1.21版本已发布
vue8.1.21版本已发布
jquery8.1.21版本已发布

Codeforces Round #267 (Div. 2) E Alex and Complicated Task_html/css_WEB-ITnose

原创
2016-06-24 11:57:18 910浏览

很不错的思维题,贪心

题目大意:给你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 #include #include #include #include #include #include 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>1;const double EPS = 1e-8;const int INF = 100000000;const int MAXN = 500000+100;struct Node{    int l,r;    int x;}nodes[MAXN];mappos,cnt;vectorb;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   



声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。