题目描述 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次访问都入堆
然后开始从第2个人的循环遍历
把每个人的n次访问都入堆
每入堆一次都伴随着另一个数据的出堆
堆里个数维持在n个
然后，当now的时间大于top的时间则出堆
好吧，思路说的不是很明白，看代码
来，上代码：
#include <cstdio>
#include <iostream>
#include <algorithm> using namespace std; struct node {
int name,now,times;
};
struct node pos[],cur_; class T_heap {
private:
int n;
struct node heap[]; public:
void up(int now)
{
if(now<=) return ;
int next=now>>;
if(heap[now].now!=heap[next].now)
{
if(heap[now].now>heap[next].now)
{
swap(heap[now],heap[next]);
up(next);
}
}
else
{
if(heap[now].name>heap[next].name)
{
swap(heap[now],heap[next]);
up(next);
}
}
} void down(int now)
{
int next=now,lc=now<<,rc=now<<|;
if(lc<=n)
{
if(heap[lc].now!=heap[next].now)
{
if(heap[lc].now>heap[next].now)
{
next=lc;
}
}
else
{
if(heap[lc].name>heap[next].name)
{
next=lc;
}
}
}
if(rc<=n)
{
if(heap[rc].now!=heap[next].now)
{
if(heap[rc].now>heap[next].now)
{
next=rc;
}
}
else
{
if(heap[rc].name>heap[next].name)
{
next=rc;
}
}
}
if(next!=now)
{
swap(heap[next],heap[now]);
down(next);
}
} void qush(struct node cur_)
{
heap[++n]=cur_;
up(n);
} void pop()
{
heap[]=heap[n--];
down();
} struct node top()
{
return heap[];
}
};
class T_heap heap; int num,n; char flag[]; bool cmp(struct node som,struct node som_)
{
if(som.times!=som_.times) return som.times<som_.times;
else return som.name<som_.name;
} int main()
{
cin>>flag;
while(flag[]=='T')
{
cin>>pos[++num].name;
cin>>pos[num].times;
cin>>flag;
}
cin>>n;
sort(pos+,pos+num+,cmp);
for(int j=;j<=n;j++)
{
pos[].now=pos[].times*j;
heap.qush(pos[]);
}
for(int i=;i<=num;i++)
{
for(int j=;j<=n;j++)
{
pos[i].now=pos[i].times*j;
cur_=heap.top();
if(cur_.now!=pos[i].now)
{
if(pos[i].now<cur_.now)
{
heap.pop();
heap.qush(pos[i]);
}
else break;
}
else
{
if(cur_.name>pos[i].name)
{
heap.pop();
heap.qush(pos[i]);
}
else break;
}
}
}
for(int i=n;i>=;i--)
{
pos[i]=heap.top();
heap.pop();
}
for(int i=;i<=n;i++) printf("%d\n",pos[i].name);
return ;
}