| C2 |
The only difference between problems C1 and C2 is that all values in input of problem C1 are distinct (this condition may be false for problem C2).
You are given a sequence ??a consisting of ??n integers.
You are making a sequence of moves. During each move you must take either the leftmost element of the sequence or the rightmost element of the sequence, write it down and remove it from the sequence. Your task is to write down a strictly increasing sequence, and among all such sequences you should take the longest (the length of the sequence is the number of elements in it).
For example, for the sequence [1,2,4,3,2][1,2,4,3,2] the answer is 44 (you take 11 and the sequence becomes [2,4,3,2][2,4,3,2], then you take the rightmost element 22 and the sequence becomes [2,4,3][2,4,3], then you take 33 and the sequence becomes [2,4][2,4] and then you take 44 and the sequence becomes [2][2], the obtained increasing sequence is [1,2,3,4][1,2,3,4]).
The first line of the input contains one integer ??n (1≤??≤2⋅1051≤n≤2⋅105) — the number of elements in ??a.
The second line of the input contains ??n integers ??1,??2,…,????a1,a2,…,an (1≤????≤2⋅1051≤ai≤2⋅105), where ????ai is the ??i-th element of ??a.
In the first line of the output print ??k — the maximum number of elements in a strictly increasing sequence you can obtain.
In the second line print a string ??s of length ??k, where the ??j-th character of this string ????sj should be ‘L‘ if you take the leftmost element during the ??j-th move and ‘R‘ otherwise. If there are multiple answers, you can print any.
5 1 2 4 3 2
4 LRRR
7 1 3 5 6 5 4 2
6 LRLRRR
3 2 2 2
1 R
4 1 2 4 3
4 LLRR
The first example is described in the problem statement.
思路：
这题其实是一个很水的模拟题。但是我卡在了如果左右两边的相同应该往哪去走。
既然不知道往哪里走，不妨两边都走试试！然后找到最大的就是答案！
1 #include <stdio.h> 2 #include <algorithm> 3 #include <iostream> 4 #include <stdlib.h> 5 #include <string> 6 #include <string.h> 7 #include <math.h> 8 #include <vector> 9 #include <queue> 10 #include <stack> 11 #include <map> 12 13 14 #define INF 0x3f3f3f3f 15 #define LL long long 16 #define MAXN 200005 17 using namespace std; 18 19 int n; 20 int a[MAXN]; 21 char str1[MAXN],str2[MAXN]; 22 23 int main() 24 { 25 scanf("%d",&n); 26 for (int i=1;i<=n;i++) 27 cin >> a[i]; 28 int l = 1; 29 int r = n; 30 int temp = 0; 31 int cnt = 0; 32 while (l<=r) 33 { 34 if (a[l]<=a[r] && a[l]>temp || (a[l]>temp && a[r]<=temp)) 35 { 36 str1[cnt++] = ‘L‘; 37 temp = a[l]; 38 l++; 39 } 40 else if (a[l]>a[r] && a[r]>temp || (a[r]>temp && a[l]<=temp)) 41 { 42 str1[cnt++] = ‘R‘; 43 temp = a[r]; 44 r--; 45 } 46 else 47 break; 48 } 49 int ans = 0; 50 l = 1; 51 r = n; 52 temp = 0; 53 while (l<=r) 54 { 55 if (a[l]<a[r] && a[l]>temp || (a[l]>temp && a[r]<=temp)) 56 { 57 str2[ans++] = ‘L‘; 58 temp = a[l]; 59 l++; 60 } 61 else if (a[l]>=a[r] && a[r]>temp || (a[r]>temp && a[l]<=temp)) 62 { 63 str2[ans++] = ‘R‘; 64 temp = a[r]; 65 r--; 66 } 67 else 68 break; 69 } 70 if (cnt>=ans){ 71 cout << cnt << endl; 72 for (int i=0;i<cnt;i++) 73 cout << str1[i]; 74 } 75 else{ 76 cout << ans << endl; 77 for (int i=0;i<ans;i++) 78 cout << str2[i]; 79 } 80 return 0; 81 }
| D |
思路：
有趣的构造题。。
设数列的和为S
先考虑和最小的一种构造方案。由题目可得，这个数列必须是一个单调上升的序列，因此和最小的数列显然就是一个首项为1，公差为1，项数为k的等差数列
如果此时S>n，那么显然是无解的
否则我们考虑往数列的某些位置加数
显然所有公差为11的等差数列都是符合题意的数列，因此我们可以先把数列的每一项都加上一个⌊n−S?⌋/k
现在还剩(n−S) mod k需要加。
前面说过，每一个公差为1的等差数列都是满足的，因此我们可以考虑每次把数列的某个后缀都加1
假设我们把从i到k的这个后缀加1，那么i必须满足
a[i] + 1 <= 2a[i-1]?，这里暴力的加就好了
如果已经加不下去了，那么就已经无解了
1 #include <algorithm> 2 #include <cstdio> 3 4 using namespace std ; 5 6 typedef long long LL ; 7 const int N=2e5+10 ; 8 9 int a[N] ; 10 int n , k ; 11 LL sum ; 12 13 int main () 14 { 15 int i ; 16 scanf("%d%d",&n,&k); 17 for ( i=1 ; i<=k ; i++ ) a[i]=i,sum+=(LL)i; 18 if ( sum>n ) return puts("NO")*0; 19 LL d=(n-sum)/k , l=n-sum-d*k; 20 while ( l ) 21 { 22 for ( i=k ; l && i>=1 ; i-- ) 23 if ( a[i]+d+1<=2*(a[i-1]+d) ) a[i]++,l--; 24 if ( l && a[k]+d+1>2*(a[k-1]+d) ) return puts("NO")*0; 25 } 26 puts("YES"); 27 for ( i=1 ; i<=k ; i++ ) printf("%lld ",a[i]+d); 28 return 0 ; 29 }
You are given two arrays ??a and ??b, both of length ??n. All elements of both arrays are from 00 to ??−1n−1.
You can reorder elements of the array ??b (if you want, you may leave the order of elements as it is). After that, let array ??c be the array of length ??n, the ??i-th element of this array is ????=(????+????)%??ci=(ai+bi)%n, where ??%??x%y is ??x modulo ??y.
Your task is to reorder elements of the array ??b to obtain the lexicographically minimum possible array ??c.
Array ??x of length ??n is lexicographically less than array ??y of length ??n, if there exists such ??i (1≤??≤??1≤i≤n), that ????<????xi<yi, and for any ??j (1≤??<??1≤j<i) ????=????xj=yj.
The first line of the input contains one integer ??n (1≤??≤2⋅1051≤n≤2⋅105) — the number of elements in ??a, ??b and ??c.
The second line of the input contains ??n integers ??1,??2,…,????a1,a2,…,an (0≤????<??0≤ai<n), where ????ai is the ??i-th element of ??a.
The third line of the input contains ??n integers ??1,??2,…,????b1,b2,…,bn (0≤????<??0≤bi<n), where ????bi is the ??i-th element of ??b.
Print the lexicographically minimum possible array ??c. Recall that your task is to reorder elements of the array ??b and obtain the lexicographically minimum possible array ??c, where the ??i-th element of ??c is ????=(????+????)%??ci=(ai+bi)%n.
4 0 1 2 1 3 2 1 1
1 0 0 2
7 2 5 1 5 3 4 3 2 4 3 5 6 5 1
0 0 0 1 0 2 4
思路：
争取让(a[i]+b[i])%n最小也就是让所以当前b[i]能取的最小值为n-a[i]?。如果不能取n-a[i]?，那么就要取n-a[i]+1，以此类推。
学会使用multset
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,a[200001]; 4 multiset<int>s; 5 int main(){ 6 scanf("%d",&n); 7 for(int i=1;i<=n;++i)scanf("%d",&a[i]); 8 for(int i=1;i<=n;++i)scanf("%d",&a[0]),s.insert(a[0]); 9 for(int x,i=1;i<=n;++i){ 10 auto it=s.lower_bound((n-a[i])%n); 11 if(it==s.end())x=*s.begin(),s.erase(s.begin()); 12 else x=*it,s.erase(it); 13 printf("%d ",(x+a[i])%n); 14 } 15 }
1 #include <stdio.h> 2 #include <algorithm> 3 #include <iostream> 4 #include <stdlib.h> 5 #include <string> 6 #include <string.h> 7 #include <math.h> 8 #include <vector> 9 #include <queue> 10 #include <stack> 11 #include <map> 12 #include <set> 13 14 15 #define INF 0x3f3f3f3f 16 #define LL long long 17 #define MAXN 200005 18 using namespace std; 19 20 const int N = 2e5 + 5; 21 int n; 22 int a[N], c[N]; 23 int main() { 24 //freopen("../in.txt","r",stdin); 25 scanf("%d", &n); 26 for(int i = 1; i <= n; i++) scanf("%d", &a[i]), c[a[i]]++; 27 int ans = 0; 28 int l, r; 29 int ansl, ansr; 30 int sum = 0; 31 for(int i = 1; i < N; i++) { 32 if(c[i] >= 1 && sum == 0) { 33 l = i; 34 sum += c[i] ; 35 }else if(c[i] > 1) { 36 sum += c[i]; 37 }else if(sum > 0){ 38 if(c[i] == 1) sum++, r = i; 39 else r = i - 1; 40 if(sum > ans) { 41 ans = sum ; 42 ansl = l; 43 ansr = r; 44 } 45 sum = 0; 46 if(c[i] == 1) { 47 sum++; 48 l = i; 49 } 50 } 51 } 52 cout << ans << ‘\n‘ ; 53 if(c[ansl] == 1) cout << ansl << ‘ ‘, ansl++ ; 54 for(int i = ansl; i <= ansr; i++) { 55 for(int j = 1; j < c[i]; j++) { 56 printf("%d ",i) ; 57 } 58 } 59 for(int i = ansr; i >= ansl; i--) { 60 printf("%d ",i); 61 } 62 return 0; 63 }
Codeforces Round #555 (Div. 3)
原文：https://www.cnblogs.com/-Ackerman/p/11261643.html
