首页 > ACM题库 > HDU-杭电 > hdu 2791 Government Help待解决[解题报告]C++
2014
02-14

hdu 2791 Government Help待解决[解题报告]C++

Government Help

问题描述 :

Two major banks in our country are knee-deep in troubles. We will call them "Bank A" and "Bank B" – hopefully you understand we absolutely cannot tell you their real names. It might ruin them.

As a logical consequence of their troubles, government comes to rescue them, preparing a set of financial "packages" that will be distributed between these two banks. However, there is one important condition: the packages will be given to the banks one by one and we need to minimize the difference between the amount given to both banks in any particular moment.Otherwise, one of the banks would gain a big advantage over the other.

For example, imagine that we have four packages with the values of 100 000, 110 000, 120 000, and 150 000. If we give the first package to the Bank A, then the second one to the Bank B, the third one to the Bank B, and the fourth package to the Bank A, the difference between the help provided to the banks will be +100 000 after the first package, -10 000 after the second one, -130 000 after the third one, and +20 000 after the last package. The maximal difference is therefore 130 000.

There is a better solution, with the maximal difference of 100 000 only: first, give 100 000 to the Bank A, then 120 000 to the Bank B, then 110 000 to the Bank A, and then 150 000 to the Bank B.

输入:

The input contains multiple sets of financial packages. Each set begins with a line containing a single positive integer N: the number of financial packages (1 ≤ N ≤ 50 000). The second line is a set of N positive integers separated by a space, all of them between 100 000 and 199 999 inclusive. These numbers specify the amount of money in individual packages. Packages can be assigned in any order, the order of numbers on the second line is therefore not important.

The last set will be followed by a line containing single zero.

输出:

The input contains multiple sets of financial packages. Each set begins with a line containing a single positive integer N: the number of financial packages (1 ≤ N ≤ 50 000). The second line is a set of N positive integers separated by a space, all of them between 100 000 and 199 999 inclusive. These numbers specify the amount of money in individual packages. Packages can be assigned in any order, the order of numbers on the second line is therefore not important.

The last set will be followed by a line containing single zero.

样例输入:

4
100000 110000 120000 150000
3
100000 100000 100000
0

样例输出:

100000-A 120000-B 110000-A 150000-B
100000-B 100000-A 100000-A


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。