F. Maximum Balanced Circle
题目链接 https://codeforces.com/contest/1157/problem/F
题意
给出 \(n\) 个数, 现在要从中选出最多的数 \(b_i,b_{i+1},\cdots,b_k\), 将这些数连成一个环, 要求两两相邻的数相差不超过 1.
最后要求输出具体的方案.
题解
一开始想了一个 dp, 似乎也可以做
这个题也不用这么复杂, 因为相差绝对值不超过 1, 直接统计一下每个数的个数就行了.
因为如果将最后的环给展开, 以每个数的值为高, 呈现出来的图形一定是先上升后下降的. 那么中间部分的数的个数一定大于等于 2, 最左边和最右边的两个数特殊考虑一下就行了.
代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N = 2e5 + 5;
- int n;
- int a[N], c[N];
- int main() {
- scanf("%d", &n);
- for(int i = 1; i <= n; i++) scanf("%d", &a[i]), c[a[i]]++;
- int ans = 0;
- int l, r;
- int ansl, ansr;
- int sum = 0;
- for(int i = 1; i <N; i++) {
- if(c[i]>= 1 && sum == 0) {
- l = i;
- sum += c[i] ;
- }else if(c[i]> 1) {
- sum += c[i];
- }else if(sum> 0){
- if(c[i] == 1) sum++, r = i;
- else r = i - 1;
- if(sum> ans) {
- ans = sum ;
- ansl = l;
- ansr = r;
- }
- sum = 0;
- if(c[i] == 1) {
- sum++;
- l = i;
- }
- }
- }
- cout <<ans <<'\n' ;
- if(c[ansl] == 1) cout << ansl << ' ', ansl++ ;
- for(int i = ansl; i <= ansr; i++) {
- for(int j = 1; j < c[i]; j++) {
- printf("%d",i) ;
- }
- }
- for(int i = ansr; i>= ansl; i--) {
- printf("%d",i);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3056548.html