首先,读完这题我一开始有点懵,分析了条件后还是不知道怎么分配比较完美,一开始想一直给最小的那个分配呗,但这不知道分配的力量是多少,没有一个界线,所以要找一个界线,最后还是看了别人的参考答案,用二分确定会变的界线,然后bool数组检查有没有达到界线,没达到的都分配力量,分配的力量要消耗的精力应该选最小值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int A[1000009];//N名士兵
int B[509];//M个训练计划
int C[509];//每个训练计划消耗的精力
int dp[100009];//dp[i]表示获得至少i点力量所需要的最少精力
int N,M,K;
bool check(int mid)
{
ll ans=0;
for(int i=1;i<=N;i++)//枚举每个士兵的初始力量值
{
//若当前士兵的初始力量值小于mid,说明要消耗精力去训练他,使他获得mid-A[i]点力量
//同时累加训练该士兵所消耗的最少精力,即dp[mid-A[i]]
if(A[i]<mid)ans=ans+dp[mid-A[i]];
}
//累加完毕后检查所消耗的总精力是否超出K,若未超出说明该方案可行,否则不可行
if(ans<=K)return true;
else return false;
}
int main()
{
cin>>N>>M>>K;
for(int i=1;i<=N;i++)cin>>A[i];
for(int i=1;i<=M;i++)cin>>B[i];
for(int i=1;i<=M;i++)cin>>C[i];
memset(dp,0x3f,sizeof(dp));//dp数组先初始化为一个极大值,代表最少消耗的精力为无穷大,后续再缩小
dp[0]=0;//获得0点力量,无需消耗精力
for(int i=1;i<=M;i++)//依次考虑每个计划
{
for(int j=0;j<100009;j++)//枚举所有能获得的力量点数
{
//不选择当前计划,消耗的精力为dp[j]
//选择当前计划,若当前能获得的力量点数大于该计划的力量点数,则消耗的精力为dp[j-B[i]]+C[i]
//若当前能获得的力量点数不大于该计划的力量点数,则消耗的精力为dp[0]+C[i]
//二者取较小值,更新dp数组
dp[j]=min(dp[j],dp[max(0,j-B[i])]+C[i]);
}
}
//下面开始二分,枚举每个士兵所有可能获得的力量点数,找出下限值
//初始区间:最少获得1点力量,保险起见右端点可以选大一点
int left=1,right=100008;
while(left<=right)
{
int mid=(left+right)/2;//计算中间值
if(check(mid))left=mid+1;//若返回true,该方案可行,则取右半区间继续验证
else right=mid-1;//不可行,取左半区间继续验证
} //退出循环时left已经移至right右侧
if(check(left))cout<<left<<endl;//最后验证一遍left是否可行
else cout<<left-1<<endl;
return 0;
}
我的做题感悟:
首先还是这种要分配的问题,多的还是用背包来做,在这个问题中,背包的“容量”可以类比为总精力消耗 K
,而每个“物品”的价值和重量则对应于训练计划提升的力量和消耗的精力。在bool函数中不需要急切的去找到dp数组的最小值,而在主函数中去完成,还有一点也是才明白的:写循环的时候什么时候从1开始,什么时候从0开始,这题为了对应士兵编号所以从1开始,后面也有一个=号。这题也是用了二分方法来查找最好的力量界线。
在题目出现这种最佳分配之类的时候,要考虑用到dp,背包,找一个最佳分配界线时考虑二分法
标签:背包,int,精力,兵营,界线,力量,分配,dp From: https://blog.csdn.net/yyyy2711/article/details/141874609