Codeforces Round #375 (Div. 2) C. Polycarp at the Radio 贪心+排序

Source

Codeforces Round #375 (Div. 2)

My Solution

贪心+排序

刚开始的时候理解题意错了，以为最小值尽可能大，最大值尽可能小，

但其实是中间贪心的过程中把最大值的 cnt[m-1].b的乐队变成最小值的乐队 cnt[0].b，直到 cnt[0].cnt 达到 n / m 就是最大的那个最小值了，而bj 的最大值不用再压缩了。

即

val[i].b 表示乐队编号， val[i].cnt 表示该乐队当前表演songs的数量

while(最小值 < int(n / m)){

如果大于m的 v[j] 还有则把这个v[j] 变成当前最小值的乐队 val[0].b;

否则把当前最大值的乐队变成当前最小值的乐队 val[0].b;

cnt++;

重新排序

}

复杂度 O(n^2)

#include 
#include 
#include 
#include 


#include 
using namespace std;
typedef long long LL;
const int maxn = 2e3 + 8;

struct p{
    int b, cnt = 0;
}val[maxn];

inline bool cmp(const p& a, const p& b)
{
    return a.cnt < b.cnt;
}

int v[maxn];
map<int, int> sz;

//priority_queue<ii, vector, greater > pq;

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 6;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, m, cnt = 0, k = 0;
    cin >> n >> m;
    for(int i = 0; i < n; i++){ cin >> v[i];
        sz[v[i]]++;
        if(v[i] > m) k++;
    }

    for(int i = 1; i <= m; i++){
        val[i-1].cnt = sz[i];
        val[i-1].b = i;
    }

    sort(val, val + m, cmp);
    //cout << val[0].cnt << " " <<  val[m-1].cnt << endl;
    while(val[0].cnt < (n / m)){ //m <= m ¹Ê val[0].cnt > 0
        //cout << "H"<<endl;
        if(k == 0){
            val[0].cnt++;
            val[m-1].cnt--;
            cnt++;
            for(int i = 0; i < n; i++){
                if(v[i] == val[m-1].b){
                    v[i] = val[0].b;
                    break;
                }
            }
        }
        else{
            k--;
            val[0].cnt++;
            cnt++;
            for(int i = 0; i < n; i++){ if(v[i] >  m){
                    v[i] = val[0].b;
                    break;
                }
            }
        }
        sort(val, val + m, cmp);
    }


    cout << val[0].cnt << " " << cnt << endl;
    for(int i = 0; i < n; i++){
        if(i != 0) cout << " " << v[i];
        else cout << v[i];
    }

    #ifdef LOCAL
    sz.clear();
    memset(val, 0, sizeof val);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

Codeforces Round #375 (Div. 2) C. Polycarp at the Radio 贪心+排序

相关推荐

UESTC 65 CD Making 贪心法

Codeforces Round #377 (Div. 2) D. Exams 二分+贪心 or 纯贪心水过

AtCoder Petrozavodsk Contest 001 D – Forest 连通块+并查集+贪心

Codeforces Hello 2018 D. Too Easy Problems 二分+贪心

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类