Problem J:Uncle Hey
The annual GaoDaoKuOI (GDKOI), an interesting programming contest, was held several weeks ago. Uncle Hey had been supposed to be a judge, but turned out to be a scheduler, which annoyed him very much. What’s going on?
During the contest, contestants might want to go out for a break. (Don’t ask why they have such a privilege. They do have anyway) However, it is not allowed that two or more contestants went out together. So, they had to go one by one, that is, First Come First Served. In case that two or more contestants posted their requests at the same time, you could safely assume that the one with the lexicographically smaller name came earlier.
It’s an annoying job, isn’t it? So, Uncle Hey wants to share the annoyance with you guys here.
Given the record of all requests like this:
T1 C1 D1
T2 C2 D2
…
Tn Cn Dn
Each line describes a request, where Ti represents the posting time of the request, and Ci represents the name of the contestant who posted the request, and Di means how long will it take for he/she to go out and come back. Note that, requests are given in no order.
You’re supposed to report all events like this: “xxx went out at time yyy” (quotes for clarity), where xxx represents the name of the contestant and yyy is the time when he/she was permitted to go. You should print the events in the non-decreasing order of the happening time. Please refer to the sample for more information.
Input:
First line contains an integer M (M ≤ 6), indicating the number of test cases.
Each test case is in the format like this:
First comes a positive integer N (N ≤ 10000), indicating the number of requests.Then N lines follows. Each line contains a positive integer T, a string C and a positive integer D, representing a request. T ≤ 10000000, D ≤ 1000, C contains no more than 20 lowercase letters.
It’s guaranteed that there are no two requests share a same name.
Output:
For each test case, print all events in the order described as above, one event per line. Print a blank line after each test case.
Sample Input:
2
1
10 lq 5
2
10 lq 5
5 wing 6
Sample Output:
lq went out at time 10
wing went out at time 5
lq went out at time 11
简单题,没涉及到什么算法,不过挺考编程能力
#include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef struct R{ int go; char name[25]; int post; int time; }R; bool cmp1(const R& a,const R& b){ if(a.post<b.post)return true; else if(a.post>b.post)return false; else if(strcmp(a.name,b.name)<0)return true; else return false; } int main(){ int n,t,k,i; cin>>n; while(n--){ cin>>t; R r[10005]; for(i=0;i<t;i++){ cin>>r[i].post>>r[i].name>>r[i].time; r[i].go=r[i].post+r[i].time; } sort(r,r+t,cmp1); cout<<r[0].name<<" went out at time "<<r[0].post<<endl; k=r[0].post+r[0].time; for(int j=1;j<t;j++){ if(r[j].post<=k){ cout<<r[j].name<<" went out at time "<<k<<endl; k+=r[j].time; } else{ cout<<r[j].name<<" went out at time "<<r[j].post<<endl; k=r[j].post+r[j].time; } } cout<<endl; } return 0; }
原文:http://blog.csdn.net/lindonglian/article/details/24190827