D. Equalize the Remainders[模拟+set中lower_bound效率问题]

D. Equalize the Remainders

题意:要求改变一个数组,使得模m后,结果为0,1,2,3,...,m-1都是n/m个,每次操作可以选择一个数+1,问至少执行多少次,并输出最终的数组

思路:模拟当前元素应该往哪个元素去改变

注意:std::set::lower_bound的复杂度为logN,而std::lower_bound的复杂度在set里是logn+n,原因大致是set是一颗平衡树,用普通的lower_bound会有额外的增量时间,具体的,不研究.

具体的,可以上stackoverflow 或者 cppreference 参考两个函数的API接差别.

#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N=4e5+5;
const int MOD=1e9+7;
int a[N],sum[N];
int cnt[N];
set<int> st;
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int n,m;
    cin >>n >> m;
    for(int i=1;i<=m;i++)   st.insert(i-1);
    const int need=n/m;
//    cout << need << endl;
    ll ans=0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        int mo=a[i]%m;
        int dest;
        if(mo>*st.rbegin())    dest=*st.begin();
        else    dest=*st.lower_bound(mo);
//        cout <<mo<<"~"<<cnt[mo]<<" "<<dest<<endl;
        if(++cnt[dest]==need) st.erase(dest)/*,cout <<"erase"<<" "<<mo<<endl;*/;
        ans+= (dest-mo+m)%m;
        a[i]+= (dest-mo+m)%m;
    }
    cout << ans << endl;
    for(int i=1;i<=n;i++)   cout << a[i] <<" ";

    return 0;
}

全部评论

相关推荐

07-24 13:43
门头沟学院 Java
longerluck...:我猜说的是“你真**是个天才”
投递美团等公司10个岗位
点赞 评论 收藏
分享
Lorn的意义:你这标个前端是想找全栈吗?而且项目确实没什么含金量,技术栈太少了,边沉淀边找吧 现在学院本想就业好一点四年至少得高三模式两年加油吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务