牛客网2018年湘潭大学程序设计竞赛 E-吃货

输入描述:

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

输出描述:

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

1
3 3
1 100
10 1000
1000000000 1001
9
10
1000000000

100
1000
1001

大量的输入输出，请使用C风格的输入输出。

看大佬的代码，先给结构体排序，再二分查找。

自己的代码

#include<bits/stdc++.h>
using namespace std;
struct head
{
	int x,y;
}a[30000];
bool cmp(head a,head b)
{
	//if(a.x<b.x) return a.x<b.x;
	if(a.x==b.x)
	{
		if(a.y>b.y)
		return a.y>b.y;
	}
	return a.x>b.x;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++)
		{
			scanf("%d%d",&a[i].x,&a[i].y);
		}
		sort(a,a+n,cmp);
		while(m--)
		{
			int q,cc=0;
			scanf("%d",&q);
			for(int i=0;i<n;i++)
			{
				if(q>=a[i].x)
				{
					printf("%d\n",a[i].y);
					cc=1;
					break;
				}
			}
			if(cc==0)
			printf("0\n");	
		}
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct eat{
    int price;
    int value;
}a[30005];
int cmp(eat a, eat b)
{
    return a.price < b.price;
}
int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int n, m, t1, t2;
        scanf("%d%d",&n,&m);
        for(int i = 0;i < n;i ++)
        {
            scanf("%d%d",&t1,&t2);
            a[i].price = t1;
            a[i].value = t2;
        }
        sort(a,a + n,cmp);
        for(int i = 1;i < n;i ++)
        {
            a[i].value = max(a[i].value,a[i-1].value);
        }
        while(m --)
        {
            int tmp, ans = 0;
            scanf("%d",&tmp);
            int l = 0, r = n - 1, mid;
            while(l <= r)
            {
                mid = (l + r) / 2;
                if(tmp < a[mid].price)
                r = mid - 1;
                else
                {
                    ans = a[mid].value;
                    l = mid + 1;
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}