优雅的序列
grace.cpp
题目描述
设一个含有n个数的序列的优雅度为满足ai＜ai+1（1≤i<n）的i的个数。现在给出一个含有n个数的序列，小X想要将这n个数调整顺序，使得新序列的优雅度最大。同样喜欢优雅的你，能否求出这个最大的优雅度呢？
输入格式：
第1行：一个整数n
第2行：n个整数，表示原始序列
输出格式：
输出1个整数，为新序列的最大优雅度
|
样例输入 |
样例输出 |
|
5 1 3 2 4 1 |
3 |
样例解释
排列方式不唯一，一种可行的排列方式为1、2、1、3、4，优雅度为3。可以通过穷举法证明这是最优方案。
数据范围
对于10%的数据，n≤10
对于40%的数据，n≤1000
对于100%的数据，n≤100000，序列中的每个数≤1000000000
水题，仔细观察之后发现只要没有重复的数，答案即为n-1。
那么就把一个数重复多次，对答案的贡献度就是一个数，所以答案为n-1-（这个数的个数-1）=n-这个数的个数。
再多添加别的数字，我们发现只要别的数的的个数比最多的数的个数少，就可以对答案产生贡献，所以同理答案=n-出现最多的数的个数
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[100031],dp[100031]={0}; int main() { // freopen("grace.in","r",stdin); //freopen("grace.out","w",stdout); int i,j; int n; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } int ans1=0; sort(a,a+n+1); a[0]=a[1]; int k=1; for(i=1;i<=n;i++) { if(a[i-1]!=a[i]) { k++; } dp[k]++; ans1=max(ans1,dp[k]); } int ans; ans=n-ans1; cout<<ans; }