
玩具
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 743 Solved: 404
[Submit][Status][Discuss]
Description
这天,小球球把所有的N辆玩具摆成一排放在地上,对于每辆玩具i,小球球都会给它涂上一个正整数value[i],以表示小球球对该玩具的喜爱程度,value[i]越小则表示他越喜爱。当然对于两辆不同的玩具u,v(u<>v),亦有可能value[i]=value[j],也就是说小球球对u,v两车的喜爱程度是一样的。
小球球很贪玩,他希望能从中间某个位置,连续的取出k辆玩具,使得这k辆车里喜爱程度最大的一辆车的喜爱程度正好等于k,且这k辆车中没有两辆车的喜爱程度是相同的。小球球希望知道k的最大值为多少。
Input
接下来N行,每行一个整数,表示value[i]。
Output
Sample Input
2
4
1
3
2
1
Sample Output
HINT
1<=Value[i]<=10^6
10%的测试数据 N<=10^5。
100%的测试数据 N<=10^6
Source
1318: [Spoj744] Longest Permutation
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 608 Solved: 366
[Submit][Status][Discuss]
Description
你的任务是找到这种类型的最长的子集。
Input
第二行,n个数,第I个数表示元素Ai
Output
Sample Input
4 1 2 3 2
Sample Output
HINT
你可以选得子集从A1开始到A4,这个子集长度为4,包含了1,2,3,4)
1<=n<=100010
Source
第一题直接划水,第二题想了想。
第二题题解:可以想到如果两个值相同的话是绝对不能在同一段的
并且它是要连续的,那我们每次加入一个节点时,求出以这个节点结尾的
最大值,怎么求,我用线段树来维护,这棵线段树是一棵权值线段树,
用full表示在这棵子树的所有叶节点是否都有了,然后每个节点记录最小,最大时间戳
表示当前子树中最早与最晚进来的时间,因为每个节点最多只会有一个时间戳,然后
对于删除,就是从头开始一旦两个相同,就将删除指针后移到当前相同的那一个位置+1
每次询问在线段树上二分,左子树如果满了,并且,是当前需要的最迟siz左子树节点就满足
然后去右子树,这是一个递归过程。
删除log n ,插入log n 每个值只会插入一次删除一次,正确答案一定有最右断点。
所以总复杂度O(n log n)
但是数据比较水,这两道题只需要输出序列的最大值即可。
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring> #define N 27
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n;
int a[N]; int main()
{
n=read();int ans=;
for (int i=;i<=n;i++)
{
int x=read();
ans=max(x,ans);
}
printf("%d\n",ans);
}