Codeforces Round #375 (Div. 2)

Codeforces Round #375 (Div. 2) - C

阅读量：6857 次

发布时间：2019-06-26

本文共 1574 字，大约阅读时间需要 5 分钟。

题目链接：http://codeforces.com/contest/723/problem/C

题意：给定长度为n的一个序列。还有一个m。现在可以改变序列的一些数。使得序列里面数字[1,m]出现次数最小的次数尽可能大。输出出现次数最小的次数。需要改变序列多少次。改变后的序列。

思路：题意有点难懂。可以发现出现次数最小的次数最大一定是(n/m).所以枚举数字[1,m]如果数字i(1<=i<=m)出现次数小于n/m,则要把序列某个数替换成i,怎么选择用哪些数来替换。应该选序列值大于m的或者序列值在[1,m]范围但是出现次数大于cnt的来替换。注意题目没有要求一定要把大于m的数都变成[1,m]。

比如数据

4 3

1 2 3 4

输出结果是

1 0

1 2 3 4

因为不管把4替换成[1,3]的哪个都不会使出现次数最小变大。

#define _CRT_SECURE_NO_DEPRECATE#include
     
        #include
      
         #include
       
        #include
        
           #include
         
            #include
          
            #include
           
            #include
            #include
             
              #include
              
               using namespace std;typedef long long int LL;const int INF = 0x3f3f3f3f;const int MAXN = 2000 + 10;int n, m, a[MAXN];map
               
                mp;int main(){ while (~scanf("%d%d", &n, &m)){ mp.clear(); for (int i = 1; i <= n; i++){ scanf("%d", &a[i]); mp[a[i]]++; } int changecnt = 0; int cnt = n / m; for (int i = 1; i <= m ; (mp[i]>=cnt?i++:i)){ //枚举[1,m] if (mp[i] < cnt){ //出现次数小于n/m int maxcnt = 0, maxid = 0; //找到一个出现次数大于n/m或者值大于m的来替换 for (map
                
                 ::iterator it = mp.begin(); it != mp.end(); it++){ if (it->first <= m){ if (it->second>cnt&&it->second > maxcnt){ maxcnt = it->second; maxid = it->first; } } else{ if (it->second > maxcnt){ maxcnt = it->second; maxid = it->first; } } } for (int j = 1; j <= n; j++){ if (a[j] == maxid){ a[j] = i; break; } } mp[i]++; mp[maxid]--; changecnt++; } } printf("%d %d\n", n / m, changecnt); for (int i = 1; i <= n; i++){ printf("%d", a[i]); printf(i == n ? "\n" : " "); } } return 0;}

转载于:https://www.cnblogs.com/kirito520/p/5930083.html

你可能感兴趣的文章