题目描述
某班有 n 个学生,编号 1∼n。
中午下课后,学生们陆续赶到食堂吃饭。
食堂只有一个打饭窗口,所以学生们要排队打饭。
第 i 个学生在第 li 分钟开始排队(当然是排在队尾)。
如果同一分钟有多个学生同时开始排队,则编号较小的学生排在编号较大的学生之前。
当一名学生排在队伍的最前端时,即轮到该名学生打饭。
每个学生打饭需要花费一分钟时间。
打到饭的学生,立即离开队伍,没打到饭的学生,在队伍里继续等待。
每个学生的耐心都是有限的。
对于第 i 个学生,如果在第 ri 分钟时,他仍在排队,且未轮到他打饭(仍有人排在他之前),那么他就会直接离开,放弃打饭。
对于每个学生,请你确定他是在第几分钟开始打饭(即排到队首)的?
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含整数 n。
接下来 n 行,每行包含两个整数 li,ri,表示第 i 个学生到达队伍的时间以及忍耐的极限时间。
保证同一组数据的 li 是非递减的。
输出格式
每组数据输出一行结果,包含 n 个整数,其中第 i 个整数表示第 i 个学生开始打饭的时间,如果这个学生直接离开,放弃打饭,则输出 0。
数据范围
前三个测试点满足 1≤n≤3。
所有测试点满足 1≤T≤1000,1≤n≤1000,1≤li≤ri≤5000。
同一测试点内所有 n 的和不超过 1000。
样例
输入样例:
2
2
1 3
1 4
3
1 5
1 1
2 3
输出样例:
1 2
1 0 2
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 10010;
int n,m,l,r;
typedef pair<int, int> PII;
int cnt;
int hh = 0, tt =0;
bool qq(int l ,int r ,queue <PII> &pr){
int x= pr.back().first,y = pr.back().second;//x到达时间,y开始打饭时间
if(l==x) //同时到达
{
if(r >= y + 1){ pr.push({l,y+1});}
else return false;
}
else //不同时到达
{
if(r >= y + 1 && l <= y + 1) {pr.push({l,y+1});}
else if(r >= y + 1 && l > y + 1) {pr.push({l,l});}
else return false;
}
// cout<<x<<" "<<y<<endl;
return true;
}
int main()
{queue <PII> pr;
cin>>n;
while (n -- )
{ pr.push({0,0});
cin>>m;
while(m--){
cin>>l>>r;
if(qq(l,r,pr))
cout<<pr.back().second<<" ";
else cout<<0<<" ";
}
puts("");
while(pr.size()) pr.pop();
}
// for(auto item :pr){
// cout<<item.first<<" "<<item.second<<endl;
// }
}