牛客网 E吃货

链接： https://www.nowcoder.com/acm/contest/105/E
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

作为一个标准的吃货，mostshy又打算去联建商业街觅食了。
混迹于商业街已久，mostshy已经知道了商业街的所有美食与其价格，而且他给每种美食都赋予了一个美味度，美味度越高表示他越喜爱这种美食。
mostshy想知道，假如带t元去商业街，只能吃一种食物，能够品味到的美食的美味度最高是多少？

输入描述:

第一行是一个整数T(1 ≤ T ≤ 10)，表示样例的个数。 以后每个样例第一行是两个整数n,m(1 ≤ n,m ≤ 30000)，表示美食的种类数与查询的次数。 接下来n行，每行两个整数分别表示第i种美食的价格与美味度d_i,c_i (1 ≤ d_i,c_i ≤ 10⁹)。 接下来m行，每行一个整数表示mostshy带t(1 ≤ t ≤ 10⁹)元去商业街觅食。

输出描述:

每个查询输出一行，一个整数，表示带t元去商业街能够品味到美食的最高美味度是多少，如果不存在这样的美食，输出0。

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int d,c;
};
bool cmp(node a,node b)
{
 
    return a.d<b.d;
 
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        node a[30005];
        int n,m,i,j;
        scanf("%d%d",&n,&m);
        int q;
 
        for(i=1;i<=n;i++)
            {
            scanf("%d%d",&a[i].d,&a[i].c);
 
            }
             sort(a+1,a+n+1,cmp);
             int p[30005];
             for(j=1;j<=n;j++)
             {
                 p[j]=a[j].d;
                 if(a[j+1].c<a[j].c)//更新性价比，保证不会多花冤枉钱
                    a[j+1].c=a[j].c;
             }
        for(i=1;i<=m;i++)
        {
            scanf("%d",&q);
             int maxx=0;
             int h=(upper_bound(p+1,p+n+1,q)-(p));
              
             maxx=a[h-1].c;
 
            
           printf("%d\n",maxx);
        }
    }
    return 0;
}