| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem F
开心的二鸣
Time Limit: 3000ms
Memory Limit: 65536kb Description
要放寒假了，二鸣开开心心的去代售点取火车票。代售点的队伍永远有着坑爹的长度，于是无聊空虚闲的蛋疼的二鸣想到如下事情： 若排在二鸣前面有n个人，编号分别从1到n，第i个人买票需要时间ti，每个人的排队时间为排在他前面所有人买票的时间和。最初时每个人的不耐烦度为0，对于第i个人若其在排队，则每单位时间不耐烦度增加vi；若其在买票，则每单位时间不耐烦度增加1；若已经买好，则会离开不耐烦度也不再增加，只留下二鸣继续苦逼排队。 那么，如何安排这n个人的排队次序使得二鸣前面队伍总的不耐烦度和最小。 Input
可能会有多组输入。每组输入第一行为用空格分隔的n(0<n≤10^5)和p，接下来n行的第i行为用空格分隔的两个整数ti、vi。所有数据均为32位整数。 n为0代表输入结束。 Output
每组输入对应一组输出,每组输出占一行。若p为0，则输出最小的不耐烦度总和，输入数据保证该值不超过有符号64位整数的表达范围。 若p为1，则输出在耐烦度总和最小的情况下的安排方案，从窗口开始到二鸣前一人为止，数据用一个空格分隔。 若有多组安排方案，以字典序小的安排方案对应答案为准。 Sample Input
3 0 1 2 2 1 1 3 3 1 1 2 2 1 1 3 0 Sample Output
8 3 1 2 Source
zqy@USTC ACM team
|