Codeforces651B Beautiful Paintings

题目链接

题意:给出n个数,随意排列使相邻的两个数右边大于左边的数对最多。

先排序,然后把每个数字出现的次数放入一个新的数组b,再排序。

假如b数组排序后是1 3 4 5,每次都以最小的为基准选出1*4个数(三对,ans+=3),然后剩为1-1,3-1,4-1,5-1即2, 3, 4,以此类推。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int a[1005];
int b[1005];
int main(){
    //freopen("a.txt", "r", stdin);
    int n;
    while(~scanf("%d", &n)){
        a[0] = -1;
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        sort(a+1, a+1+n);
        int ans = 0, cnt = 0, k = 1;
        for(int i = 1; i <= n; i++){
            if(a[i]!=a[i-1] && i!=1){
                b[k++] = cnt;
                cnt = 1;
            }else{
                cnt++;
            }
            if(i==n)
                b[k++] = cnt;
        }
        //for(int i = 1; i < k; i++) cout << b[i] << endl;
        b[0] = 0;
        sort(b, b+k);
        int w = k-2;
        for(int i = 1; i < k; i++){
            ans += (w--)*(b[i]-b[i-1]);
        }
        cout << ans << endl;
    }
    return 0;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法