题解：P7023 [NWRRC2017] Equal Numbers

_GW_ · 2024-12-22 16:18:35 · 题解

思路

1. 首先，若要让不同的数的数量减少，必须要把某个数赶尽杀绝，全部同化成其他数，其代价是数组内该数的出现次数。

2. 其次，考虑操作的策略，要么改成数组内的其他数（记为方案 1），要么就干脆一劳永逸，改成所有数的公倍数（记为方案 2）。

3. 然后，再考虑如何在这两种方案中抉择，发现把第一次使用方案 1 时，极有可能没有让不同的数的数量减少，如果已经使用了一次方案 1，那么后续再使用方案 1 是显然比方案 2 只优不劣的。即可发现要么全用方案 1，要么全用方案 2。

4. 之后就好办了，详见代码。

code

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int a[N],cnt[N],vis[N],sum[N],n,m,k,x,y,b[N],c[N],d[N],T,len;
int main()
{
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>d[i];
    vis[d[i]]++;//输入并记录每个数的出现次数 
  }
  sort(d+1,d+1+n);
  for(int i=1;i<=n;i++)
  {
    if(d[i]!=d[i-1])
    {
      a[++m]=d[i];
      c[m]=vis[d[i]];//手动去重，并记录每个数改成所有数的最小公倍数的代价 （即其出现次数）
    }
  }
  for(int i=1;i<=m;i++)
  {
    for(int j=a[i]*2;j<=1e6;j+=a[i])//这个东西是nlogn的 ,但我不会证 
    {
      if(vis[j])
      {
        b[++len]=vis[a[i]];//寻找每个元素在数组组中是否有倍数，并记录该元素改成其倍数的代价（即其出现次数） 
        break;
      }
    }
  }
  sort(c+1,c+1+m);
  sort(b+1,b+1+len);//记得排序，毕竟选越小的越优 
  for(int i=1;i<=n;i++)
  {
    sum[i]=sum[i-1]+c[i];cnt[i]=cnt[i-1]+b[i];//前缀和优化 
  }
  int x=0,y=0;
  for(int i=0;i<=n;i++)
  {
    while(x+1<=m&&sum[x+1]<=i) ++x;
    while(y+1<=len&&cnt[y+1]<=i) ++y;//对于每个k，看是变成最小公倍数更优还是变成数列中的其他数更优 
    cout<<(m-max(x-1,y))<<' '; 
  }cout<<'\n';
  return 0;
}