HDUOJ---1171

http://acm.hdu.edu.cn/showproblem.php?pid=1171

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

HDUOJ-----(1072)Nightmare(bfs)

Nightmare Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K ...

3387
来自专栏ml

HDUOJ ---1423 Greatest Common Increasing Subsequence(LCS)

Greatest Common Increasing Subsequence Time Limit: 2000/1000 MS (Java/Others)   ...

2845
来自专栏ml

hdu 1695 GCD(莫比乌斯反演)

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

3676
来自专栏数据结构与算法

POJ2409 Let it Bead(Polya定理)

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

1002
来自专栏小樱的经验随笔

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

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

3014
来自专栏ml

HDUOJ----2952Counting Sheep

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

3367
来自专栏小樱的经验随笔

HDU 2504 又见GCD(最大公约数与最小公倍数变形题)

又见GCD Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

2703
来自专栏ml

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

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

2765
来自专栏ml

专题练习---(数论)莫比乌斯反演

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

36911
来自专栏Hadoop实操

CENTOS6.5安装CDH5.12.1(二)

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

3916

扫码关注云+社区