请问大佬们D 题本质是在问这个问题吗

现有n组物品,其中每组物品都对应着一个价值u以及一个重量w。给定一个特定的数值k,需要解决的问题是:从这些物品中进行选择,在确保所选物品的总价值大于或等于k的前提下,使得所选物品的重量总和达到最小,那么这个最小的重量总和是多少呢?

全部评论
void solve(){ ll n,y,sum=0; cin>>n>>y; vector<int>a(n); for(int i=0;i<n;i++){ cin>>a[i]; sum+=a[i]; } if(sum>=y){ cout<<0<<'\n&(30945)#39;; return; } y-=sum; ll ans=1e18; for(int high=0;high<64;high++){ // 枚举最高位  vector<int>b; // 只选择有0的位  for(auto i:a)if(!(i>>high&1))b.push_back(i); int m=b.size(); ll v=(1LL<<high)*m; ll w=1LL<<high; if(v>=y){ ans=w; break; } else { //  使用低位满足后 贪心减重 break 否则 continue  vector<int>cnt2(64,0); for(auto i:b){ for(int j=0;j<32;j++){ if(i>>j&1)cnt2[j]++; } } // 加入低位 int i; for(i=0;i<=high-1;i++){ if(m-2*cnt2[i]<=0)continue; v+=(1LL<<i)*(m-2*cnt2[i]); w+=1LL<<i; if(v>=y)break; } if(i==high)i--; if(v>=y){ // 能满足要求 就尽量减少重量  v-=y; for(int j=i-1;j>=0;j--){ if(m-2*cnt2[j]<=0)continue; if((1LL<<j)*(m-2*cnt2[j])<=v){ v-=(1LL<<j)*(m-2*cnt2[j]); w-=1LL<<j; } } ans=w; break; } } } cout<<ans<<'\n&(30945)#39;; 终于试出来了
点赞 回复 分享
发布于 04-04 14:31 辽宁
这里的wi是1,2,4,8,16,可以贪心选择
点赞 回复 分享
发布于 04-03 21:50 湖南

相关推荐

不愿透露姓名的神秘牛友
07-07 13:47
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务