贪心_限制数字的范围的取模的技巧_偶数的性质_1883_C. Raspberries

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10;

int a[N];

void solve()
{
	int n,k;
	cin>>n>>k;
	
	for(int i=0;i<n;i++)
		cin>>a[i];
	
	int ans=1e9;
	for(int i=0;i<n;i++)
	{
		if(a[i]%k==0)
			ans=0;
		int t=k-(a[i]+k)%k;
		ans=min(ans,t);
	}
	
	if(k==4)
	{
		int cnt=0;
		for(int i=0;i<n;i++)
			if(a[i]%2==0)
				cnt++;
		
		if(cnt>=2)
			ans=0;
		else if(cnt==1&&n-cnt>=1)
			ans=min(ans,1);
		else if(n-cnt>=2)
			ans=min(ans,2);
	}
	
	cout<<ans<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin>>t;
	
	while(t--)
		solve();
	
	return 0;
}

该题是一个一千分的动态规划和数学，虽然和我之前学的动态规划大相径庭

我感觉这题更像是一个贪心

首先是所有的数据都非常小，然后给的除数也是在一到五这个范围内，一根本不用考虑，因为一可以整除所有的正整数

剩下一个四和三个质数

四的话，需要另外考虑，两个偶数的乘积一定可以被四整除，因为偶数可以分解质因子出来一个二，两个偶数两个二，相乘就是四

对于另外几个除数，只需要考虑，一个数组元素经过最少多少次操作可以被该除数整除，贪心策略去一个最小值即可

下面这一行代码可以保证数组元素一定在除数的范围内，属于一个非常常见的技巧

int t=k-(a[i]+k)%k;

偶数的个数大于二，并且除数是四的话，答案就是零，有一个偶数和不少于一个奇数，答案是用贪心策略和一取最小值，没有偶数，只有两个以上的奇数，答案是贪心策略和二取最小值

这个是div 3的第三个题，还是没有非常大的难度

代码007普通

打赏 收藏 海报 链接