2830 蓬莱山辉夜
题目描述 Description
在幻想乡中，蓬莱山辉夜是月球公主，居住在永远亭上，二次设定说她成天宅在家里玩电脑，亦称NEET姬
一天，她要她帮忙升级月球的网络服务器，应为注册用户过多（月兔和地球上的巫女都注册了……），所以作为代理管理员（俗称网管）的她，非常蛋疼。
注册用户格式：
TouhouMaiden 2004 200
其中前面的Touhoumaiden是预设，不做更改，第一个数是标识，第二个数是每次接受信息访问的间隔用时。
你要做的事，就是给定一群用户及n，求出这n次信息访问中，访问到了谁？
presented by Izayoi sakuya
输入描述 Input Description
以题目预设格式输入，另起一行以‘#’结束，在其一行输入n
输出描述 Output Description
n行，每行输出第行次后，信息访问到了谁？若在一个时间有若干少女被访问到，输出字典序最小的那位少女的标识
样例输入 Sample Input
TouhouMaiden 2004 200
TouhouMaiden 2005 300
#
5
样例输出 Sample Output
2004
2005
2004
2004
2005
数据范围及提示 Data Size & Hint
标识和每次信息访问间隔均在integer内，n<=10000
原本是要用到堆，但深搜+时间即可搞定
数据有点少但也都够变态了
本题描述有问题。题目中说：“若在一个时间有若干少女被访问到，输出字典序最小的那位少女的标识”，然而样例是按字典序全部输出
本题的意思：许多人排队等待被访问，他们每人都有一个编号（输入数据每一行的第一个数字），和一个时间，时间为等待时间（输入数据每一行的第二个数字）+已花费时间。他们排队的顺序为先按等待时间排序，若等待时间相同再按编号的字典序排序。然而每个人都想多次被访问，所以他们每次被访问完后，都会再去插队，再等待他们相应的等待时间再次被访问，访问完了之后再去插队……他们并不是老老实实的去排队，而是插队，插到等待时间+已花费时间比他还要长的人的前面。（也就是总时间少的人先被访问）
所以可以建立一个小根堆，每次取出堆中的第一个元素，输出编号，加上等待时间再放进堆里去，循环n次。
#include<iostream>
#include<cstdio>
#include<algorithm>
struct node
{
int a,b,c;//a编号，b已花费时间，c等待时间
}e[];
using namespace std;
int n,s,i,l[];//s堆heap中元素的个数，l用于存放时间相同的少女的编号
char c[];
node heap[];//堆
bool cmp(node k,node p)
{
return k.b<p.b;
}
void insert(node k)//向堆中加入元素
{
s++;
heap[s]=k;
int p=s;
while(p>&&k.b<heap[p/].b)
{
heap[p]=heap[p/];
p/=;
}
heap[p]=k;
}
void heapify(int k)//维护小根堆
{
int left=k*,right=k*+;
int minn=k;
if(left<=s) minn=heap[minn].b<heap[left].b ? minn:left;
if(right<=s) minn=heap[minn].b<heap[right].b ? minn:right;
if(minn!=k)
{
swap(heap[minn],heap[k]);
heapify(minn);
}
}
node get()//取出堆中第一个元素
{
node k=heap[];
heap[]=heap[s];
s--;
heapify();
return k;
}
int main()
{
cin>>c;
while(c[]!='#')
{
i++;
scanf("%d%d",&e[i].a,&e[i].b);
e[i].c=e[i].b;
insert(e[i]);
cin>>c;
}
scanf("%d",&n);
while(n)
{
bool ok=false;
node h=get();//取出堆中的第一个元素
int o=h.a;//这次要输出的元素的编号
int su=;//相同时间的少女的个数
while(h.b==heap[].b) //有少女在相同时间被访问到
{
ok=true;
l[++su]=h.a;//存进去
h.b+=h.c;//加上等待时间
insert(h);//再放回堆里
h=get();//再取出堆得第一个元素
o=min(o,h.a);
}
l[++su]=h.a;
h.b+=h.c;
insert(h);
//如过存在几个少女同一时间被访问到的情况，那根据上面的while，最后一个同一时间的少女没有取出来放入l数组，所以要加进去
//如果不存在几个少女同一时间被访问的情况，语句l[++su]=h.a执行没有影响，实际有作用的是后两句
if(ok)
{
sort(l+,l+su+);//按字典序输出
for(int i=;i<=su;i++)
printf("%d\n",l[i]);
n-=su;
continue;
}
printf("%d\n",o);//没有少女在同一时间被访问，直接输出编号
n--;
}
}