洛谷P2370 yyy2015c01 的 U 盘

传送门

题目背景

在 2020 年的某一天，我们的 yyy2015c01 买了个高端 U 盘。

题目描述

你找 yyy2015c01 借到了这个高端的 U 盘，拷贝一些重要资料，但是你发现这个 U 盘有一些问题：

这个 U 盘的传输接口很小，只能传输大小不超过 LL 的文件。
这个 U 盘容量很小，一共只能装不超过 SS 的文件。
但是你要备份的资料却有很多，你只能备份其中的一部分。

为了选择要备份哪些文件，你给所有文件设置了一个价值 V_iV
i
​
，你希望备份的文件总价值不小于 pp。

但是很快你发现这是不可能的，因为 yyy2015c01 的传输接口太小了，你只有花钱买一个更大的接口（更大的接口意味着可以传输更大的文件，但是购买它会花费更多的钱）。

注意：你的文件不能被分割（你只能把一个文件整个的传输进去，并储存在U盘中）,

你放在 U 盘中文件的总大小不能超过 U 盘容量。

现在问题来了：你想知道，在满足 U 盘中文件价值之和不小于 pp 时，最小需要多大的接口。

输入格式

第 11 行，三个正整数 n,p,Sn,p,S 分别表示文件总数，希望最小价值 pp ，U 盘大小。

接下来 nn 行，每行两个正整数 W_{i},V_{i}W
i
​
,V
i
​
，表示第 ii 个文件的大小和价值。

输出格式

U容量盘恢复U容量盘恢复方法

application/x-rar 4星 超过75%的资源 250KB

下载

输出一个正整数表示最小需要的接口大小。

如果无解输出 No Solution!。

输入输出样例

输入 #1复制
3 3 5
2 2
1 2
3 2
输出 #1复制
2
输入 #2复制
2 3 505
1 2
500 1
输出 #2复制
500
输入 #3复制
3 3 2
2 2
1 2
3 2
输出 #3复制
No Solution!
输入 #4复制
4 5 6
5 1
5 2
5 3
1 1
输出 #4复制
No Solution!

说明/提示

1 \le n, W_i, S \le 10^31≤n,W
i
​
,S≤10
3
，1 \leq V_i \leq 10^61≤V
i
​
≤10
6
，1 \leq p \leq 10^91≤p≤10
9
。

数据较小，请勿乱搞。

样例解释 11：买一个大小为 22 接口，把物品 11 、22 放进\text{U}U盘。

样例解释 22：买一个大小为 500500 的接口。

样例解释 33：本来可以买大小为 22 的接口，可是 U 盘容量放不下足够的文件。

如果数据出现疏漏，请联系出题人 a710128

向本题主人公 yyy2015c01 同学致敬！

上代码：

#include
using namespace std;
long long n,V,S,s[1010],v[1010],l=0,r=10000,mid,gs,dp[1010],ss[1010],vv[1010];
int check(long long x)
{
	gs=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]<=x)
		{
			ss[++gs]=s[i];
			vv[gs]=v[i];
		}
	}
	for(int i=1;i<=gs;i++)//背包模板
	{
		for(long long j=S;j>=ss[i];j--)
		{
			dp[j]=max(dp[j],dp[j-ss[i]]+vv[i]);
		}
	}
	if(dp[S]>=V)
	{
		for(int i=0;i<=S;i++)
		{
			dp[i]=0;
		}
		return 1;
	}
	else
	{
		for(int i=0;i<=S;i++)
		{
			dp[i]=0;
		}
		return 0;
	}
}
int main()
{
	scanf("%lld%lld%lld",&n,&V,&S);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&s[i],&v[i]);
	}
	for(;l<=r;)//二分答案
	{
		mid=(l+r)/2;
		if(check(mid))//背包判断
		{
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	if(l>1000)
	{
		cout<<"No Solution!";//不要忘了
		return 0;
	}
	cout<<l;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64