「BZOJ1307」玩具
Description
小球球是个可爱的孩子，他喜欢玩具，另外小球球有个大大的柜子，里面放满了玩具，由于柜子太高了，每天小球球都会让妈妈从柜子上拿一些玩具放在地板上让小球球玩。 这天，小球球把所有的N辆玩具摆成一排放在地上，对于每辆玩具i，小球球都会给它涂上一个正整数value[i]，以表示小球球对该玩具的喜爱程度，value[i]越小则表示他越喜爱。当然对于两辆不同的玩具u,v(u<>v)，亦有可能value[i]=value[j]，也就是说小球球对u,v两车的喜爱程度是一样的。 小球球很贪玩，他希望能从中间某个位置，连续的取出k辆玩具，使得这k辆车里喜爱程度最大的一辆车的喜爱程度正好等于k，且这k辆车中没有两辆车的喜爱程度是相同的。小球球希望知道k的最大值为多少。
Input
第一行一个整数N，表示小球球拥有的玩具数量。 接下来N行，每行一个整数，表示value[i]。
Output
一个整数k，即答案。
Sample Input
6
2
4
1
3
2
1
2
4
1
3
2
1
Sample Output
4
HINT
1<=Value[i]<=10^6
10%的测试数据 N<=10^5。
100%的测试数据 N<=10^6
题解
见bzoj1318
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,ans; int a[1000015],next[1000015],last[1000015]; ll sum[1000015]; void cal(int x) { int len=0,r=inf; for(int i=x;i;i--) { if(a[i]==1&&i!=x)break; len=max(len,a[i]); r=min(next[i],r); if(i+len-1<r&&i+len-1<=n) { if(sum[i+len-1]-sum[i-1]==(ll)len*(len+1)/2)ans=max(len,ans); } } } void solve() { memset(last,127,sizeof(last)); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]; for(int i=n;i;i--) { next[i]=last[a[i]]; last[a[i]]=i; } for(int i=1;i<=n;i++) if(a[i]==1)cal(i); } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); solve(); for(int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]); solve(); printf("%d\n",ans); return 0; } |
Subscribe
计数器 9857470
OI 课件=>
OI 课件=>