时间限制: 1 s空间限制: 32000 KB题目等级 : 黄金 Gold 题目描述Description
在幻想乡中,蓬莱山辉夜是月球公主,居住在永远亭上,二次设定说她成天宅在家里玩电脑,亦称NEET姬
一天,她要她帮忙升级月球的网络服务器,应为注册用户过多(月兔和地球上的巫女都注册了……),所以作为代理管理员(俗称网管)的她,非常蛋疼。
注册用户格式:
TouhouMaiden 200
其中前面的Touhoumaiden是预设,不做更改,第一个数是标识,第二个数是每次接受信息访问的间隔用时。
你要做的事,就是给定一群用户及n,求出这n次信息访问中,访问到了谁?
presented by Izayoi sakuya
输入描述Input Description
以题目预设格式输入,另起一行以‘#’结束,在其一行输入n
输出描述Output Description
n行,每行输出第行次后,信息访问到了谁?若在一个时间有若干少女被访问到,输出字典序最小的那位少女的标识
样例输入Sample Input
TouhouMaiden 200
TouhouMaiden 300
#
5
样例输出Sample Output
数据范围及提示Data Size & Hint
标识和每次信息访问间隔均在integer内,n<=10000
原本是要用到堆,但深搜+时间即可搞定
数据有点少但也都够变态了
可以尝试模拟。
代码实现:
1 #include<cstdio> 2 int n,m,time,now,sc[3000],xyb; 3 int name[1000010],jg[1000010][2]; 4 char ch[30]; 5 int main(){ 6while(scanf("%s",&ch)){ 7 if(ch[0]=='#') break; 8 scanf("%d%d",&name[m],&jg[m][0]); 9 m++;10}11scanf("%d",&n);12while(n){13 now=1000000000;14 for(int i=0;i<m;i++){15 while(jg[i][1]<=time) jg[i][1]+=jg[i][0];16 xyb=jg[i][1]-time;17 if(xyb==now){18 int j=sc[0];19 sc[0]++;20 sc[sc[0]]=i;21 while(name[sc[j]]>name[i]&&j){22 sc[j+1]=sc[j];sc[j]=i;j--;23 }24 }25 if(xyb<now) sc[0]=1,sc[1]=i,now=xyb;26 }27 for(int i=1;i<=sc[0]&&n;i++){28 printf("%d\n",name[sc[i]]);29 n--;30 }31 time+=now;32}33return 0;34 }
一开始我连j和j--都没有,都让我对了2/3的点。。。
题目来源:洛谷
如果觉得《蓬莱山辉夜》对你有帮助,请点赞、收藏,并留下你的观点哦!