[Login|Register]
Problems

Status

Rank

Problem 1355
开心的二鸣
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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.5ms with 1 query(s).