equal numbers

给你一个n长度的数组，让你修改0到n次，问每次修改后能剩下不同个数的最小数是多少；

这里有了两种做法，一种是变成他们的lcm这样的话，修改后答案应该是减去改过的个数然后在加一

另一种就是数字修改成序列中的倍数，比如如果序列中有4和8，修改一次把4变成8，这样剩下的数字就只有一个；比较这两个做法，找出更小的就好了

做法就是，一种把原来次数从小到大排序，然后一个个变，另一种就是把能变成序列中其他数字的数的个数从小到大排，然后一次次跑就可以了

#include<bits/stdc++.h>

#define sf scanf

#define pf printf

#define si(a) a.size()

#define vi vector<int>

#define scf(x) scanf("%d",&x)

#define scff(x,y) scanf("%d%d",&x,&y)

#define rep(i,a,n) for (int i=a;i<n;i++)

#define per(i,a,n) for (int i=a;i>=n;i--)

#define mm(x,b) memset((x),(b),sizeof(x))

#define IO(x) freopen("x.in","r",stdin);freopen("x.out","w",stdout);

#define scfff(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define de(a) cout << #a << " = " << a << endl

#define dd(a) cout << #a << " = " << a << " "

typedef long long ll;

using namespace std;

const double eps=1e-8;

const int N=3e5+2;

map<int,int> mp;

int a1[N],a2[N];

int main()

{

	IO(equal);

	int n;scf(n);

	int maxn=0;

	rep(i,0,n)

	{

		int x;scf(x);

		maxn=max(maxn,x);

		mp[x]++;

	}

	int tot1=0,tot2=0;

	rep(i,1,maxn+1)

	{

		if(mp[i])

		{

			a1[tot1++]=mp[i];

			for(int j=i+i;j<=maxn;j+=i)

			{

				if(mp[j])

				{

					a2[tot2++]=mp[i];

					break;

				}

			}

		}

	}

	sort(a1,a1+tot1);

	sort(a2,a2+tot2);

	cout<<tot1;

	int sum1=0,sum2=0;

	int pos1=0,pos2=0;

	rep(i,1,1+n)

	{

		while(pos1<tot1&&sum1+a1[pos1]<=i)

		sum1+=a1[pos1++];

		while(pos2<tot2&&sum2+a2[pos2]<=i)

		sum2+=a2[pos2++];

		int ans=min(tot1-pos1+1,tot1-pos2);

		if(ans==0) ans=1;

		cout<<" "<<ans;

	}

	return 0;

}

巴特西

equal numbers

最新文章

热门文章