K: 自闭
K: 自闭
内存限制：128 MB时间限制：1 S标准输入输出
题目描述
世界上的大佬太多了，菜鸡们纷纷自闭并来到心理诊所寻求治疗，心理诊所的每一个医生有不同的开始上班时间，能力 a 和收费 c，能力为 a 的医生可以治好自闭程度小于或等于 a 的菜鸡。菜鸡们都很穷，所以他们只想要能治好他们的最便宜的医生，请你告诉他们当前能治好他们病的最便宜的医生的价格。(假设治疗在瞬间完成，同一个医生可以连续接待任意个客人)
输入格式
第一行一个正整数 T(T<=5),表示数据的组数
每组数据第一行一个正整数 n(n <= 10^5)，表示接下来有 n 行。
接下来 n 行中，若第一个数为 0，则接下来两个正整数 a,c 表示有一个能力为 a，收费为 c 的医生上班了。若第一个数为 1，则接下来有一个正整数 b，表示有一个自闭程度为 b 的菜鸡来寻求治疗(1<=a,b,c <= 10^9)。
输出格式
对每个寻求治疗的菜鸡，输出一个整数表示治疗需要的花费，如果没有医生能治好他，输出“-1”。
输入样例 复制
1
8
1 19
0 17 5
0 1 6
1 12
1 15
0 5 7
0 3 9
1 3
输出样例 复制
-1
5
5
5
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,t;
double a,b;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
map<int,int> yi;
for(int i=0;i<n;i++)
{
int zz;
map<int,int>::iterator it1;
map<int,int>::iterator it2;
scanf("%d",&zz);
if(!zz)
{
int a,b;
scanf("%d%d",&a,&b);
yi[a] = b;
it1=yi.find(a);
it2=it1;
it1++;
if(it2->second<it1->second||it1==yi.end())
it1=it2;
it2=it1;
for(it2--;it2!=yi.end();it2--)
{
if(it2->second>it1->second)
it2->second=it1->second;
else
break;
}
}
else
{
int b;
scanf("%d",&b);
if(yi.upper_bound(b)==yi.end())
printf("-1\n");
else
printf("%d\n",yi.upper_bound(b)->second);
}
}
}
return 0;
}
评论