题目链接：http://codeforces.com/contest/1157/problem/F
题意：在含有n个元素的数组里选择元素，使得构成一个元素最多的环(环满足相邻元素差的绝对值<=1)
先处理集合里的元素，统计每个元素的出现次数，并且将集合排好序，去重。
因为构成一个这样的环一定是这样的情况：元素值先上升，后下降，并且下降的元素即为上升元素的倒序，
所以当我们构造这样一个环时，我们就要去找出现次数>=2的元素，多余2的部分全放上升元素这边，下降元素均为1个
#include #include #include #include #include #include #include #include <set> #include #include <string> #include #include #define INF 0x3f3f3f3f using namespace std; typedef long long ll; static const int MAX_N = 2e5 + 5; static const ll Mod = 2009; int a[MAX_N], cnt[MAX_N]; void solve(){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int k; while(scanf("%d", &k) != EOF){ for(int i = 0; i 0; for(int i = 0; i i){ scanf("%d", &a[i]); cnt[a[i]]++; } sort(a, a + k); int tot = unique(a, a + k) - a; //保持单调递增，便于构造 int ansl = 0, ansr = 0, ansle = cnt[a[0]]; for(int i = 0, j; i j){ j = i + 1; int le = cnt[a[i]]; while(j 1] == 1 && cnt[a[j]] >= 2) le += cnt[a[j++]]; int r = j - 1; if(j 1] == 1) r = j, le += cnt[a[j]]; if(le > ansle) ansle = le, ansl = i, ansr = r; } printf("%d\n", ansle); if(ansl == ansr){ for(int i = 0; i "%d%c", a[ansl], i == ansle - 1 ? '\n' : ' '); continue; } for(int i = 0; i "%d ", a[ansl]); //升序起点 for(int i = ansl + 1; i i){ for(int j = 1; j "%d ", a[i]); //留一个给下降元素 } for(int i = 0; i "%d ", a[ansr]); //升序终点 for(int i = ansr - 1; i > ansl; --i) printf("%d ", a[i]); putchar('\n'); } } int main() { solve(); return 0; }
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号