Dreamoon is a big fan of the Codeforces contests.
One day, he claimed that he will collect all the places from 11 to 5454 after two more rated contests. It's amazing!
Based on this, you come up with the following problem:
There is a person who participated in nn Codeforces rounds. His place in the first round is a1a1, his place in the second round is a2a2, ..., his place in the nn-th round is anan.
You are given a positive non-zero integer xx.
Please, find the largest vv such that this person can collect all the places from 11 to vv after xx more rated contests.
In other words, you need to find the largest vv, such that it is possible, that after xx more rated contests, for each 1≤i≤v1≤i≤v, there will exist a contest where this person took the ii-th place.
For example, if n=6n=6, x=2x=2 and a=[3,1,1,5,7,10]a=[3,1,1,5,7,10] then answer is v=5v=5, because if on the next two contest he will take places 22 and 44, then he will collect all places from 11 to 55, so it is possible to get v=5v=5.
The first line contains an integer tt (1≤t≤51≤t≤5) denoting the number of test cases in the input.
Each test case contains two lines. The first line contains two integers n,xn,x (1≤n,x≤1001≤n,x≤100). The second line contains nn positive non-zero integers a1,a2,…,ana1,a2,…,an (1≤ai≤1001≤ai≤100).
For each test case print one line containing the largest vv, such that it is possible that after xx other contests, for each 1≤i≤v1≤i≤v, there will exist a contest where this person took the ii-th place.
5
6 2
3 1 1 5 7 10
1 100
100
11 1
1 1 1 1 1 1 1 1 1 1 1
1 1
1
4 57
80 60 40 20
输出
5
101
2
2
60
题目有点绕，仔细读一下就是给你n个数然后 从1开始数，如果在这n个数中没有出现就补上这个数然后m--,看最长的这个连续是对少。
例如 4 2
1 4 5 6
那么最长的连续就是
1 2 3 4 5 6
#include<bits/stdc++.h> #include<map> using namespace std; int main() { int t; cin>>t; while(t--) { map<int,int>q; int n,m; int ans=0; cin>>n>>m; int a[105]; for(int i=0; i<n; i++) { cin>>a[i]; q[a[i]]=1; } int k=1; for(int i=1; i<=m;) { //cout<<k<<endl; if(q[k]==1) { ans++; } else { ans++; i++; } k++; } for( k; k<=100; k++) { if(q[k]==1) ans++; if(q[k]==0) break; } cout<<ans<<endl; } return 0; }
The sequence of mm integers is called the permutation if it contains all integers from 11 to mm exactly once. The number mm is called the length of the permutation.
Dreamoon has two permutations p1p1 and p2p2 of non-zero lengths l1l1 and l2l2.
Now Dreamoon concatenates these two permutations into another sequence aa of length l1+l2l1+l2. First l1l1 elements of aa is the permutation p1p1 and next l2l2 elements of aa is the permutation p2p2.
You are given the sequence aa, and you need to find two permutations p1p1 and p2p2. If there are several possible ways to restore them, you should find all of them. (Note that it is also possible that there will be no ways.)
The first line contains an integer tt (1≤t≤100001≤t≤10000) denoting the number of test cases in the input.
Each test case contains two lines. The first line contains one integer nn (2≤n≤2000002≤n≤200000): the length of aa. The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n−11≤ai≤n−1).
The total sum of nn is less than 200000200000.
For each test case, the first line of output should contain one integer kk: the number of ways to divide aa into permutations p1p1 and p2p2.
Each of the next kk lines should contain two integers l1l1 and l2l2 (1≤l1,l2≤n,l1+l2=n1≤l1,l2≤n,l1+l2=n), denoting, that it is possible to divide aa into two permutations of length l1l1 and l2l2 (p1p1 is the first l1l1 elements of aa, and p2p2 is the last l2l2 elements of aa). You can print solutions in any order.
6
5
1 4 3 2 1
6
2 4 1 3 2 1
4
2 1 1 3
4
1 3 3 1
12
2 1 3 4 5 6 7 8 9 1 10 2
3
1 1 1
2
1 4
4 1
1
4 2
0
0
1
2 10
0
思路： 这个题关键就是想到如果从1到n最大的数n,并且没有重复出现，也就是种类数是n,那么从这些数肯定都是大于等于1小于等于n,知道这个就好做了，下面看代码
#include<bits/stdc++.h> #include<map> #include<vector> using namespace std; int main() { int t; cin>>t; while(t--) { map<int,int>q; pair<int,int>t1[200005]; pair<int,int>t2[200005]; int n,ans=0; int Max1=0,Max2=0; vector<int>G; cin>>n; int a[200005]; for(int i=1; i<=n; i++) { cin>>a[i]; } for(int i=1; i<=n; i++) { if(a[i]>Max1) { Max1=a[i]; t1[i].first=Max1; } else { t1[i].first=Max1; } if(q[a[i]]==0) { ans++; q[a[i]]=1; t1[i].second=ans; } else t1[i].second=ans; } ans=0; q.clear(); for(int i=n; i>=1; i--) { if(a[i]>Max2) { Max2=a[i]; t2[i].first=Max2; } else { t2[i].first=Max2; } if(q[a[i]]==0) { ans++; q[a[i]]=1; t2[i].second=ans; } else t2[i].second=ans; } ans=0; for(int i=1;i<n;i++) { if(t1[i].first==t1[i].second) { if(t2[i+1].first==t2[i+1].second) { if(t1[i].second+t2[i+1].second==n) { ans++; G.push_back(i); } } } } cout<<ans<<endl; for(int i=0;i<G.size();i++) { cout<<G[i]<<" "<<n-G[i]<<endl; } } return 0; }