topcoder srm608 div1 300分题

时间：2014-02-09 16:15:16 阅读：441 评论：0 收藏：0 [点我收藏+]

题目：

Problem Statement

TopCoder admin mystic_tc is sitting in front of a table. He found N sealed boxes of candies on the table.

He is not sure how many candies each box contains. However, he knows the following information:

The total number of candies in the boxes is C.
For each i, box i (0-based index) contains between low[i] and high[i] candies, inclusive.

You know that mystic_tc eats candies as follows: first he chooses a subset of the boxes, then he opens them and eats all the candies he found inside. He wants to eat at least X candies. And as he is smart, he will always choose a subset of boxes for which he is sure that they must contain at least X candies.

You are given the ints C and X, and the vector <int>s low and high. Return the smallest number of boxes mystic_tc may choose.

Definition

Class:	MysticAndCandies
Method:	minBoxes
Parameters:	int, int, vector <int>, vector <int>
Returns:	int
Method signature:	int minBoxes(int C, int X, vector <int> low, vector <int> high)
(be sure your method is public)

Limits

Time limit (s):	2.000
Memory limit (MB):	256

Constraints

low and high will contain between 1 and 50 elements, inclusive.

low and high will contain the same number of elements.

Each element of low and high will be between 1 and 10,000,000, inclusive.

For each i, high[i] will be greater than or equal to low[i].

C will be between the sum of all elements of low and the sum of all elements of high, inclusive.

X will be between 1 and C, inclusive.

Examples

{1, 2, 3, 4, 5}

{1, 2, 3, 4, 5}

Returns: 3

Here he knows the exact number of candies in each box. The best strategy is to open boxes 2, 3, and 4 (0-based indices). This way he will get 3+4+5 = exactly 12 candies.

{5, 2, 3}

{49, 48, 47}

Returns: 2

Open box 0 and box 2.

{3, 9, 12, 6, 15}

{8, 12, 20, 8, 15}

Returns: 2

Open box 2 and box 4.

207581165

172146543

{4725448, 2753824, 6019698, 4199708, 4070001, 3589497, 5358499, 3637585, 5393667, 2837466,
2747807, 2918199, 3638042, 5199002, 3072044, 3858909, 3762101, 3657754, 3218704, 3888861,
3195689, 4768935, 3137633, 4124272, 4125056, 6087486, 3632970, 3620489, 2748765, 5917493,
3958996, 3335021, 3517186, 5543440, 2951006, 3403270, 3299481, 3093204, 4092331}

{5702812, 6805664, 6823687, 5337687, 4286533, 4999849, 6567411, 4563235, 6618139, 6260135,
6249469, 3821449, 5963157, 6385012, 4255959, 5786920, 6112817, 4103918, 6371537, 4231698,
3409172, 6806782, 5623563, 4511221, 6407338, 6491490, 5209517, 6076093, 6530132, 6111464,
5833839, 6253088, 5595160, 6236805, 5772388, 5285713, 5617002, 4650978, 5234740}

Returns: 31

43873566

32789748

{2053198, 2175819, 4260803, 1542497, 1418952, 5000015, 1381849, 2462882, 6466891, 1827580, 6943641, 5775477}

{2827461, 3726335, 5410505, 4781355, 4925909, 5621160, 7325774, 5025476, 7876037, 8072075, 6979462, 6647628}

Returns: 7

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

分析：

从1）这个例子来看，要看low数组，比如5,3两个加起来为8，说明至少有8，那么2个盒子即可。

从2）这个例子来看，要看high数组，比如8,12,8加起来来28，那么一共C=58,也就是说剩下的两个盒子至少有30.

故最终结果是从上面两个中取更小值。

代码：

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class MysticAndCandies {
public:
	int minBoxes(int, int, vector <int>, vector <int>);
};

int MysticAndCandies::minBoxes(int C, int X, vector <int> low, vector <int> high) {
	sort(low.begin(),low.end(),greater<int>());
	int ret1 = 0;
	int sum1 = 0;
	for(int i=0;i<low.size();i++)
	{
		sum1+=low[i];
		ret1++;
		if(sum1>=X)
			break;
	}
	int ret2 = 0;
	int sum2 = 0;
	sort(high.begin(),high.end());
	for(int i=0;i<high.size();i++)
	{
		sum2+=high[i];
		ret2++;
		if(sum2>=C-X)
		{
			if(sum2!=C-X)
				ret2--;
			break;
		}
	}
	return min(ret1,(int)low.size()-ret2);
}


//Powered by [KawigiEdit] 2.0!

topcoder srm608 div1 300分题

原文：http://blog.csdn.net/wangyuquanliuli/article/details/18992427

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)