一看题目,就想了一个绝逼会TLE 的方法,于是就开始想怎么做才好……然后想到一种方法,因为最长的数列肯定是同一个数,所以每次处理的时候只要把相同数字的位置处理出来就好,然后进行比较,但是没有想到可以用指针前后游动来控制范围,所以这个想法还是N*N的复杂度,所以一直没有上手敲……= =好弱啊。
看了别人的题解,发现自己就差这临门一脚了……这种方法以后要get
所以总的思路就是,把相同数字都放在一块,同时保留原位置。在每个数字块中进行指针的前后扫描。如果指针扫描到的当前位置的费用仍旧小于k,指针就继续右移,如果大于k,那么这时候右指针就不能动了,把左指针,就是记录初始位置的指针右移,把费用减去左指针右移的费用,知道费用小于k,就可以把右指针继续右移。
然后……对手指……WA在了奇怪的地方……先贴个代码……
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> using namespace std; #define maxn 100100 struct node { int val,pos; }que[maxn]; int cmp(node a,node b) { if(a.val==b.val) return a.pos<b.pos; return a.val<b.val; } int main() { int n,d; freopen("in.txt","r",stdin);freopen("outto.txt","w",stdout); while(~scanf("%d%d",&n,&d)) { int i,j,k; int maxx=0; for(i=1;i<=n;i++) { scanf("%d",&j); que[i].val=j; que[i].pos=i; } sort(que+1,que+1+n,cmp); int l,r; l=r=1; // for(i=1;i<=n;i++) printf("%d ",que[i].val);printf("\n");for(i=1;i<=n;i++) printf("%d ",que[i].pos);printf("\n"); for(i=1;i<=n;) { l=r; que[r-1].pos=que[r].pos-1; int flag=que[r].val; int sum=0,len=0; while(que[l].val==flag&&que[r].val==flag&&l<=r) { if(sum+que[r].pos-que[r-1].pos-1>d) { if(maxx<len) maxx=len; sum-=que[l].pos-que[l-1].pos-1; l++; len--; // printf("minue sum=%d len=%d \n",sum,len);system("pause"); } else { sum+=que[r].pos-que[r-1].pos-1; len++; r++; // printf("plus sum=%d len=%d \n",sum,len);system("pause"); if(maxx<len) maxx=len; } } i=r; } printf("%d\n",maxx); } return 0; }