Equalize the Remainders 【CodeForces - 999D】【思维】

mac2025-03-02  3

题目连接

题目大意

有n个数的序列,有一个m,保证m被n整除,每次操作可以任选一个数使其加一。问操作多少次可以使得这些数取模m得到的1到m-1的个数都为n/m

解题思路

我们开一个set记录取余后小于n/m的数,然后枚举每个数字。取余小于n/m的就不用管,大于的让他加1编程大于等于他最小的那个set里的数

#include<bits/stdc++.h> using namespace std; const int N=2e5+5; long long a[N],num[N]; set<long long>s; int main() { int n,m; scanf("%d %d",&n,&m); for(int i=1; i<=n; i++) { scanf("%lld",&a[i]); num[a[i]%m]++; } for(int i=0; i<m; ++i) if(num[i]<n/m) s.insert(i); long long ans=0; set<long long>::iterator it; for(int i=1; i<=n; i++) { int t=a[i]%m; if(num[t]<=n/m) continue; it=s.lower_bound(t); if(it!=s.end()) { num[t]--; a[i]+=*it-t; ans+=*it-t; num[*it]++; if(num[*it]==n/m) s.erase(*it); } else { a[i]+=m-t+*s.begin(); ans+=m-t+*s.begin(); num[t]--; num[*s.begin()]++; if(num[*s.begin()]==n/m) s.erase(*s.begin()); } } printf("%lld\n",ans); for(int i=1; i<=n; i++) printf("%lld%c",a[i],i==n?'\n':' '); return 0; }
最新回复(0)