大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
没什么特殊的想法
就是看自己很久没有更新关于题解类的文章了而已
（其实这是我好久之前做的， 只是把它从洛谷博客搬到了这里而已）
首先分析题目要二分
他长成这个亚子太二分了
所以就要二分
最好是先排一下序吧
这样我们在输入的时候就能顺便处理出l和r的值， 考虑我们二分的是一个接口的大小， 所以我们的答案肯定是在最大的接口和最小的接口之间啊， 所以这样做是可行的， 而且会让我们的程序跑的更快一些。
然而并没有什么卵用。
and 关于二分边界问题， 可以用一个ans来储存答案
然后check函数跑一遍01背包就好啦
The Last:
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int N = 1100; int n, p, s, w[N], v[N], l = N, r, mid, ans = -1, f[N]; bool check(int x) { memset (f, 0, sizeof (f)); for(int i = 1; i <= n; i++) if (w[i] <= x) for(int j = s; j >= w[i]; j--) f[j] = max(f[j], f[j - w[i]] + v[i]); if (f[s] < p) return false; return true; } int main() { scanf("%d%d%d", &n, &p, &s); for(int i = 1; i <= n; i++) { scanf("%d%d", &w[i], &v[i]); if(w[i] > r) r = w[i]; if(w[i] < l) l = w[i]; } while(l < r) { mid = (l + r) >> 1; if(check(mid)) { ans = mid; r = mid; } else l = mid + 1; } if(ans != -1) printf("%d\n", ans); else printf ("No Solution!\n"); return 0; }
谢谢收看， 祝身体健康！
转载于:https://www.cnblogs.com/yanxiujie/p/11609867.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/182792.html原文链接：https://javaforall.net
