首先，读完这题我一开始有点懵，分析了条件后还是不知道怎么分配比较完美，一开始想一直给最小的那个分配呗，但这不知道分配的力量是多少，没有一个界线，所以要找一个界线，最后还是看了别人的参考答案，用二分确定会变的界线，然后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,背包，找一个最佳分配界线时考虑二分法
