洛谷p2370yyy2015c01的U盘题解

分手后的思念是犯贱 2023-06-02 15:51 18阅读 0赞

没什么特殊的想法

就是看自己很久没有更新关于题解类的文章了而已

（其实这是我好久之前做的， 只是把它从洛谷博客搬到了这里而已）

[题目][Link 1]

首先分析题目要二分

![1692048-20190929201503125-1471719946.png][]

他长成这个亚子太二分了

所以就要二分

最好是先排一下序吧

这样我们在输入的时候就能顺便处理出l和r的值， 考虑我们二分的是一个接口的大小， 所以我们的答案肯定是在最大的接口和最小的接口之间啊， 所以这样做是可行的， 而且会让我们的程序跑的更快一些。

然而并没有什么卵用。

and 关于二分边界问题， 可以用一个ans来储存答案

[一篇很好的关于边界问题的文章][Link 2]

然后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

[Link 1]: https://www.luogu.org/problem/P2370
[1692048-20190929201503125-1471719946.png]: /images/20230601/7252482bf3b74e7bb95d1e454bf75909.png
[Link 2]: https://baijiahao.baidu.com/s?id=1607027944170585153