[NPSC] 2011決賽 F. 田忌賽馬
題目連結:http://contest.cc.ntu.edu.tw/npsc2011/finalSen_release.zip
不難發現在贏多少匹馬上有單調性,所以可以二分搜答案,驗證的方法用個greedy的方法,就盡量挑能贏他的馬跟他打,也就是最強的跟最強的比,如果打不贏就改成拿最廢的跟他換,大概這樣吧
不難發現在贏多少匹馬上有單調性,所以可以二分搜答案,驗證的方法用個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);
}
留言
張貼留言