首页 > ACM题库 > HDU-杭电 > hdu 2260 Difficulty control待解决[解题报告]C++
2014
01-04

hdu 2260 Difficulty control待解决[解题报告]C++

Difficulty control

问题描述 :

LL is very sensitive to the difficulty of ACM problems. He can assign each problem a positive integer from [1,10000000] to denote its difficulty ( although he has only ACed about 1000 problems ^_^ ). Now, there are N problems in his mind. He want to choose some of them to hold a contest and the total difficulty of all problems in the contest is as near as possible to M.

输入:

For each case, the first line is two positive integers N and M (1<=N<=26). Followed by N lines. Each line contains the problem’s ID ( a single capital letter ) and its difficulty.

输出:

For each case, the first line is two positive integers N and M (1<=N<=26). Followed by N lines. Each line contains the problem’s ID ( a single capital letter ) and its difficulty.

样例输入:

3 10
A 4
B 12
C 8

样例输出:

2
A C

Hint
"A C", "B" and "C" all reach the request. So, the answer is "A C", which comes earliest in lexicography order.


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3