[NPSC] 2011決賽 F. 田忌賽馬

題目連結:http://contest.cc.ntu.edu.tw/npsc2011/finalSen_release.zip

---

不難發現在贏多少匹馬上有單調性，所以可以二分搜答案，驗證的方法用個greedy的方法，就盡量挑能贏他的馬跟他打，也就是最強的跟最強的比，如果打不贏就改成拿最廢的跟他換，大概這樣吧

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define N 10000

struct hr{
	lld a,b;
};

lld oppo[N+5];
hr my[N+5];

lld n,k;
vector<lld> cur;
inline bool isOK(lld);
inline int fJiao();

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		lld l=-1,r=100000000;
		scanf("%lld%lld",&n,&k);
		for(int i=0;i<n;i++)scanf("%lld%lld",&my[i].b, &my[i].a);
		for(int i=0;i<n;i++)scanf("%d",&oppo[i]);
		sort(oppo, oppo+n,[](lld a,lld b){return a>b;});
		bool jj = isOK(r);
		if(!jj){
			puts("-1");
		}else{
			while(r-l!=1){
				lld mid=(l+r)/2;
				bool jj = isOK(mid);
				if(jj) r=mid;
				else l=mid;
			}
			printf("%lld\n",r);
		}
	}
	return 0;
}

inline bool isOK(lld x){
	int win=0, cWhere=0;
	cur.clear();
	for(int i=0;i<n;i++) cur.push_back(my[i].a*x+my[i].b);
	sort(cur.begin(), cur.end(),[](lld a,lld b){return a>b;});
	for(int i=0;i<n;i++){
		if(cur[cWhere]>oppo[i]){
			cWhere++;
			win++;
		}
	}
	return (win >= k);
}