B:小红不想做鸽巢原理
一道贪心题:
思路首先我们观察k是否是数组中所有数字和的倍数,如果是直接全部取完输出0就行
否则--
按照题意,贪心的来想,我们要尽可能的将数组中的多的数变成0..也就是把他们拿完一个不剩,先算出来最多可以拿下多少次,然后我们从数组中的最小值开始遍历。因为从最小值开始取,我们就可以走得更远。拿空的a[i]更多。赛时居然想着从最大的开始装,糊涂了。后来有高人指点。。才过了
代码:
/* */
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f;
const int MAX = 1e5+7;
int a[MAX];
void solve()
/*算数开ll 存图用int*/
{
int n,k;
cin>>n>>k;
int sum = 0,cnt;
for(int i=1;i<=n;i++)
cin>>a[i],sum+=a[i];
//把尽可能多的数变成0 越小越好变
sort(a+1,a+1+n);//从小开始装
if(sum % k == 0){
cout<<0;
return;
}else{
cnt = sum/k;//最多装几次
int t = 0;
for(int i=0;i<n;i++)
{
t+=a[i];
if(t<(cnt*k))a[i]=0;//装到这个位置还能装
else
break;//从这里开始 接下来就不能装了
}
}
int ans = 0;
for(int i=1;i<=n;i++)
{
if(a[i] != 0)ans++;
}
cout<<ans;
}/*算数开ll 存图用int*/
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);
cout.tie(0);
//cout<<fixed<<setprecision(2);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
C:小红不想做完全背包
一道动规经典题,由于本人是dp盲,所以记录一下。
思路:
在有限的数中选择一些数,他们满足加起来的和是p的倍数。求最小的选择数。
-- dp[i] 在所有数中选择的和满足%p=i的最小选择数个数
那么我们最后求得答案就是dp[0]了。
怎么初始化呢?
对于每个数 如果他是p得倍数,那么答案毋庸置疑就是1。因为我们选它就满足题意。
所以对于每个数,我们不妨先%p,对答案无影响,算数范围还更少。
a[i]%p之后,她一定就是小于p得了。那么现在在数组中选择它%p肯定还是它。那么我们 就可以初始化dp数组 - dp[a[i]] = 1
状态转移方程:
对于模完p的每一个a[i],它可能通过一步走到的数的范围在(a[i] + (0 ~ p))%p。
那么让j 遍历 0~p 。nex(可能到达的点)= (a[i]+(0~p))%p
dp[ne] = min(dp[ne],dp[j]+1). -- 在满足j的条件下 我只需要在数组中多选一个a[i]就行了。
代码:
/* */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int MAX = 1e5+7;
int a[2010];
int dp[2010];//dp[i]表示在所有的数中选若干个使得%p=i的最小选择数
int n,p;
void solve()
/*算数开ll 存图用int*/
{
cin>>n>>p;
memset(dp,INF,sizeof dp);//默认无穷 表示选不到
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
{
a[i]%=p;
dp[a[i]] = 1;//表示在当前数组里面 我最少选择1个数就可以满足它%p=a[i] 也就是选它本身
for(int j=0;j<p;j++)
{
int nex = (a[i]+j)%p;//在a[i]的基础上偏移 即a[i]可能能到达的所有位置
dp[nex] = min(dp[nex],dp[j]+1);//在满足dp[j]的条件下 我再选一个a[i]就可以到达nex 所以加1
}
}
cout<<dp[0];//在所有数中选择一些数 他们的和%p==0 最小的选择个数
}/*算数开ll 存图用int*/
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
cout.tie(0);
//cout<<fixed<<setprecision(2);
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}