# Big Event in HDU

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 18439    Accepted Submission(s): 6457

Problem Description

Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don't know that Computer College had ever been split into Computer College and Software College in 2002. The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0<N<1000) kinds of facilities (different value, different kinds).

Input

Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 -- the total number of different facilities). The next N lines contain an integer V (0<V<=50 --value of facility) and an integer M (0<M<=100 --corresponding number of the facilities) each. You can assume that all V are different. A test case starting with a negative integer terminates input and this test case is not to be processed.

Output

For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.

Sample Input

2 10 1 20 1 3 10 1 20 2 30 1 -1

Sample Output

20 10 40 40

Author

lcy

简单的DP

``` 1 #include<iostream>
2 #include<cstdlib>
3 using namespace std;
4 typedef struct Node
5 {
6     int value;
7     int num;
8 }node;
9 int cmp( const void *a, const void *b)
10 {
11     return (*(node*)b).value-(*(node*)a).value;
12 }
13 int main()
14 {
15     int n,i,sum,count,min;
16     node arr[301];
17    while(cin>>n,n>0)
18    {
19        for(sum=i=0;i<n;i++)
20        {
21            cin>>arr[i].value>>arr[i].num;
22            sum+=arr[i].value*arr[i].num;
23        }
24          qsort(arr,n,sizeof(arr[0]),cmp);
25          min=0;
26        for(count=i=0;i<n;i++)
27        {
28            while(arr[i].num)
29            {
30                if(count+arr[i].value<=sum/2)
31                {
32                    count+=arr[i].value;
33                }
34                arr[i].num--;
35            }
36            if(min<count)
37            {
38                min=count;
39             }
40        }
41     cout<<sum-min<<" "<<min<<endl;
42    }
43 return 0;
44 }```

657 篇文章64 人订阅

0 条评论

## 相关文章

### CENTOS6.5安装CDH5.12.1(二)

[root@ip-172-31-6-148~]# hadoop fs -mkdir -p /fayson/test

41260

### 专题练习---（数论）莫比乌斯反演

GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32...

377110

### HDU 1711 Number Sequence(KMP裸题，板子题，有坑点)

Number Sequence Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/3...

31340

### HDUOJ-------2493Timer(数学 2008北京现场赛H题)

Timer Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

27440

30330

### [Hadoop大数据]——Hive部署入门教程

Hive是为了解决hadoop中mapreduce编写困难，提供给熟悉sql的人使用的。只要你对SQL有一定的了解，就能通过Hive写出mapreduce的程...

50250

### hdu---(1054)Strategic Game(最小覆盖边)

Strategic Game Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/3...

28850

1.2K120

### POJ2409 Let it Bead(Polya定理)

"Let it Bead" company is located upstairs at 700 Cannery Row in Monterey, CA. As...

11020

### HDUOJ----2952Counting Sheep

Counting Sheep Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/327...

35370