P8160 - Paired Up

内存限制：128 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：44 通过：19

Farmer John finds that his cows are each easier to milk when they have another cow nearby for moral support. He therefore wants to take his MM cows (M≤1,000,000,000M≤1,000,000,000, MM even) and partition them into M/2M/2 pairs. Each pair of cows will then be ushered off to a separate stall in the barn for milking. The milking in each of these M/2M/2 stalls will take place simultaneously.

To make matters a bit complicated, each of Farmer John's cows has a different milk output. If cows of milk outputs A and B are paired up, then it takes a total of A+B units of time to milk them both.

Please help Farmer John determine the minimum possible amount of time the entire milking process will take to complete, assuming he pairs the cows up in the best possible way.

农夫约翰发现，一头奶牛在产奶时，如果附近有另一头奶牛作为精神支柱，那么它的产奶量就会大大增加。

因此，他想把他的 M 头奶牛分成 M/2 对。

然后，每对奶牛将被领到牛棚中一个单独的位置上挤奶。

M/2个位置上的挤奶将同时进行。

让事情变得复杂一点的是，每头奶牛都有不同的产奶量。

如果产奶量为 A 和 B 的两头奶牛配对，则总共需要 A+B 个单位的时间来产奶。

请帮助约翰确定完成整个挤奶过程所需的最短时间，假设他以最佳方式将奶牛配对。

The first line of input contains NN (1≤N≤100,0001≤N≤100,000). Each of the next NN lines contains two integers xx and yy, indicating that FJ has xx cows each with milk output yy (1≤y≤1,000,000,0001≤y≤1,000,000,000). The sum of the xx's is MM, the total number of cows.

第一行包含整数。

接下来行，每行包含两个整数 x，表示约翰有头产奶量为的奶牛。

上述行，所有 x 的和即为 M，也就是奶牛的总数。

Print out the minimum amount of time it takes FJ's cows to be milked, assuming they are optimally paired up.
输出以最佳方式将奶牛配对的情况下，完成整个挤奶过程所需的最短时间。

Here, if the cows with outputs 8+2 are paired up, and those with outputs 5+5 are paired up, the both stalls take 10 units of time for milking. Since milking takes place simultaneously, the entire process would therefore complete after 10 units of time. Any other pairing would be sub-optimal, resulting in a stall taking more than 10 units of time to milk.

USACO 2017 US Open Contest, Silver

8160: Paired Up

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签