K: 自閉
K: 自閉
內(nèi)存限制：128 MB時間限制：1 S標(biāo)準(zhǔn)輸入輸出
題目描述
世界上的大佬太多了，菜雞們紛紛自閉并來到心理診所尋求治療，心理診所的每一個醫(yī)生有不同的開始上班時間，能力 a 和收費(fèi) c，能力為 a 的醫(yī)生可以治好自閉程度小于或等于 a 的菜雞。菜雞們都很窮，所以他們只想要能治好他們的最便宜的醫(yī)生，請你告訴他們當(dāng)前能治好他們病的最便宜的醫(yī)生的價格。(假設(shè)治療在瞬間完成，同一個醫(yī)生可以連續(xù)接待任意個客人)
輸入格式
第一行一個正整數(shù) T(T<=5),表示數(shù)據(jù)的組數(shù)
每組數(shù)據(jù)第一行一個正整數(shù) n(n <= 10^5)，表示接下來有 n 行。
接下來 n 行中，若第一個數(shù)為 0，則接下來兩個正整數(shù) a,c 表示有一個能力為 a，收費(fèi)為 c 的醫(yī)生上班了。若第一個數(shù)為 1，則接下來有一個正整數(shù) b，表示有一個自閉程度為 b 的菜雞來尋求治療(1<=a,b,c <= 10^9)。
輸出格式
對每個尋求治療的菜雞，輸出一個整數(shù)表示治療需要的花費(fèi)，如果沒有醫(yī)生能治好他，輸出“-1”。
輸入樣例 復(fù)制
1
8
1 19
0 17 5
0 1 6
1 12
1 15
0 5 7
0 3 9
1 3
輸出樣例 復(fù)制
-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;
}
評論
圖片
表情