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 条评论
登录 后参与评论

相关文章

来自专栏Hadoop实操

CENTOS6.5安装CDH5.12.1(二)

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

41260
来自专栏ml

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

            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
来自专栏ml

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

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

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

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

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

30330
来自专栏xingoo, 一个梦想做发明家的程序员

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

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

50250
来自专栏ml

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

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

28850
来自专栏Hadoop实操

Hive多分隔符支持示例

如何将上述事例数据加载到Hive表(multi_delimiter_test)中,表结构如下:

1.2K120
来自专栏数据结构与算法

POJ2409 Let it Bead(Polya定理)

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

11020
来自专栏ml

HDUOJ----2952Counting Sheep

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

35370

扫码关注云+社区

领取腾讯云代金券