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