沉鱼落雁
题源：https://www.cometoj.com/contest/65/problem/B?problem_id=3683
题目描述
胖头鱼在苦恼“沉鱼落雁”是什么好吃的东西，这很显然是因为他成语没背够。
于是他决定开始背成语。胖头鱼身为鱼界大佬，背成语的姿势自然也和常人不一：
他会先将所有要背的成语一字排开，比较难背的成语会重复出现，最多重复 3 次 (也就是出现次数可能为 1, 2 或 3)。这样就得到了一个可能有重复元素的成语序列，然后他会将这个序列打乱顺序，并按打乱后的顺序背下去。为了均匀的背所有成语，提高背成语的效率，相同成语在打乱后的序列中出现位置的最小间隔自然是越大越好。 (编号为 a 和 b (a<b) 的两个位置的间隔定义为 b-a-1)
现在胖头鱼把打乱前的成语序列给你，你需要帮他打乱顺序，使得相同成语的最小间隔最大。
你不需要输出确切的方案，仅求出最小间隔的最大值即可。
特别地，当每种成语都只出现一次时，把最小间隔的最大值视为nn。
输入描述
第一行一个整数 n (1<=n<=1e5)，表示成语序列长度为 n。同一个成语最在序列中最多出现 3 次。
接下来 n 个整数 a1,a2,...,an(a<=ai<=1e9) 表示一个成语序列，每个正整数都代表一个成语，两个成语不同当且仅当值不同。
输出描述
输出一个整数，表示最小间隔的最大值。
样例输入 1
9 5 4 3 1 3 1 1 5 5
样例输出 1
2
样例解释 1
其中一組可行方案是1 3 5 1 3 5 1 4 5，容易验证没有比 2 更大的答案。
样例输入 2
5 1 2 3 4 5
样例输出 2
5
题意：给n个数，可以重新排序，不过要相同元素最小间隔最大
反正当时没做出来，手动滑稽
题解：唉，不想了，复制官方的，看完后感觉太坑了
嗯，应该是没脑子的人、
#include <math.h> #include <iostream> #include<cstring> #include <algorithm> using namespace std; int a[100009]; int b[100009]; int main() { int n; cin>>n; for(int i=0; i<n; i++) { cin>>a[i]; } sort(a,a+n); int ans1=-1; int ans2=-1; int k=0; int x=0,y=0,z=0; for(int i=0; i<n;) { if(a[i]==a[i+1]&&a[i+1]==a[i+2]) {i+=3; x++; } if(a[i]==a[i+1]&&a[i+1]!=a[i+2]) { i+=2; y++; } if(a[i]!=a[i+1]) { i++; z++; } } if(x!=0)cout<<x+y+z/2-1; if(x==0&&y!=0)cout<<y-1+z; if(x==0&&y==0)cout<<n; }
完结，撒花，没脑子的先溜了
投递海天集团等公司10个岗位 >
