首页 > 代码库 > [SinGuLaRiTy] 2017-03-30 综合性测试
[SinGuLaRiTy] 2017-03-30 综合性测试
【SinGuLaRiTy-1014】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.
对于所有的题目：Time Limit：1s | Memory：256 MB
第一题：完美序列
【题目描述】
给你一个长度为n(1<=n<=100,000)的自然数数列，其中每一个数都小于等于10亿，现在给你一个k，表示你最多可以删去k类数。数列中相同的数字被称为一类数。设该数列中满足所有的数字相等的连续子序列被叫做完美序列，你的任务就是通过删数使得该数列中的最长完美序列尽量长。
【输入】
第一行两个整数N,K。
接下来N行，每行1个整数，表示第i个数。
【输出】
最长的完美序列的长度。
【样例数据】
| 样例输入 | 样例输出 |
9 1 2 7 3 7 7 3 7 5 7 | 4 |
【STD Code】
#include<iostream>#include<cstdio>#include<algorithm>#include<cstdlib>#include<cmath>#include<cstring>using namespace std;int ans;int kind[200000];struct node{ int value; int pos;};node data[200000];int cmp_value(node a,node b){ return a.value<b.value;}int cmp_origin(node a,node b){ return a.pos<b.pos;}int main(){ int n,k; int t,now,contain,l; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&data[i].value); data[i].pos=i; } sort(data+1,data+n+1,cmp_value); now=1; t=data[1].value; for(int i=1;i<=n;i++) if(data[i].value=http://www.mamicode.com/=t) data[i].value=now; else { now+=1; t=data[i].value; data[i].value=now; } sort(data+1,data+n+1,cmp_origin); contain=0; l=1; for(int i=1;i<=n;i++) { if((kind[data[i].value]==0)&&(contain<=k)) { contain+=1; kind[data[i].value]+=1; ans=max(ans,kind[data[i].value]); } else if((kind[data[i].value]==0)&&(contain>k)) { kind[data[i].value]+=1; kind[data[l].value]-=1; while(kind[data[l].value]!=0) { l+=1; kind[data[l].value]-=1; } l+=1; ans=max(ans,kind[data[i].value]); } else { kind[data[i].value]+=1; ans=max(kind[data[i].value],ans); } } printf("%d",ans); return 0;}
【题目分析】
别的先不说，看到仅有100000个数字，数据范围却是1000000000,就说明我们首先要对这个序列进行离散化。在这里，可以开一个结构体，定义两个值：value和pos，value表示值，pos表示这个数原本在序列的哪一个位置，先用一次sort对value进行排序，更改值的大小（也就是离散化的中心操作），接着再来一次sort，按pos排序，以此将序列的位置排布还原为原来的序列。
下面，我们就来看看这道题的中心思路：设置一个“移动窗口”。也就是说，定义两个变量：L，R，来记录可能答案的潜在区间。在最开始，我们将L，R初始化为0，即L，R将从序列的最左端开始向右扫描。由于题目中有要求“仅能删除k类数”，那么，当窗口刚刚开始移动时，我们可以先保持L不动，使R右移，与此同时，不断更新在该窗口内存在的数的种类（当然，你也要算出此时的最优解），当种类达到k+1种时，就说明当前区间已经塞满啦，此时要想继续使窗口移动，就要使L+=1,更新之后，再让R+=1......以此类推，不断使窗口移动下去，直到扫描至序列末端，此时的答案就是整个序列中的完美序列的最优解了。
[SinGuLaRiTy] 2017-03-30 综合性测试