codeforces 490 div3 D. Equalize the Remainders

标签: CF  贪心  STL

这里写图片描述这里写图片描述

题目大意:

给你n个数和一个m,要求余数为0-m-1的数的数量正好是n/m,m保证是n的因子,每个数只能执行加的操作,最后输出操作的次数以及修改后的数组结果。

解题思路:

主题思想是贪心,就是让那些余数值超过n/m的数向离他最近且余数值没有满足条件的数“移动”。这里的“移动”有个巧妙的处理,就是利用STL集合中的set.lower_bound()函数,集合中保存那些未满足条件的余数值,lower_bound()函数返回第一个大于原值的的迭代器位置,如果该值存在,那么我们就向哪里“移动”,否则说明当前余数就是最大的,它不能向比它大的余数哪里“移动”了。
那么由于题意只能执行+的操作,那么我们调用set.begin()函数得到未满足条件的第一个余数值,这是原值增加超过模值后取模的结果,相当于一个闭合环。
具体细节在代码中标注了。想到用lower_boung()函数是个较难的过程,代码细节也较难实现。这个题很考验代码功底,不知为什么我用vector标记余数WA到意识模糊。。可能数据太大了?。。。。
代码如下:

#include<iostream>
#include<cstdio>
#include<fstream>
#include<set>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<iomanip>
#include<cstdlib>
#include<list>
#include<queue>
#include<stack>
#include<algorithm>
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define meminf(a) memset(a,inf,sizeof(a))
#define HASHP 13331;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define MAXN 200010
ll a[MAXN];
ll book[MAXN];
int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  //freopen("test.txt","r",stdin);
  //freopen("output.txt","w",stdout);
  int n,m;
  cin>>n>>m;
  int pi=n/m;
  //vector<int> v[MAXN];不知为什么用这个一直WA
  set<ll> p;//保存需要增加的余数
  set<ll>::iterator it;
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    book[a[i]%m]++;
  }
  for(int i=0;i<m;i++)
   if(book[i]<pi)p.insert(i);//插入数量小于平均值的余数
  ll result=0;//结果
  for(int i=0;i<n;i++)
  {
    int  temp=a[i]%m;//余数
    if(book[temp]>pi)//只处理余数数量大于平均值的值
    {
      it=p.lower_bound(temp);//先找到第一个大于该余数的迭代器位置
      if(it!=p.end())//如果有
      {
        result+=*it-temp;//结果加上这个移动次数
        a[i]+=*it-temp;//修改这个数的值
        book[*it]++;//对应迭代器余数的项数量+1
        book[temp]--;//被修改了,所以-1
        if(book[*it]==pi)p.erase(*it);//如果这个余数数量增加到了平均值,删除它
      }
      else//数量多的余数本身值小于目标元素
      {
        result+=(m-temp+*p.begin());//因为只能执行+的操作,所以集合头部就是最近的
        a[i]+=(m-temp+*p.begin());
        book[*p.begin()]++;//后面同理
        book[temp]--;
        if(book[*p.begin()]==pi)p.erase(*p.begin());
      }
    }
  }
  cout<<result<<endl;
  for(int i=0;i<n;i++)cout<<a[i]<<' ';
  cout<<endl;
  return 0;
}
原文链接:加载失败,请重新获取