UAPC 2011 G Everything Starts With Your Vote

問題

n個のキャラクターが居て、彼らの得票数は現在それぞれx[i]である。
この中でお気に入りのキャラクターがm個与えられる。
お気に入りのキャラクターにl票を好きなように投票して、k位以上のキャラクターがなるべく多くなるようにしたい。

k位以上になれるキャラクターの最大値を求めよ。

方針

何人がk位以上に入れるかについて二分探索。
m人がk位になるためには、お気に入りじゃないキャラクターのm-k+1位に勝つことが必要。
その票数を足してやれば、m人がk位になるための必要票数が求まる。

ソースコード

struct S{
  char s[11];
  int x;
  bool operator<(const S &r)const{
    if(x!=r.x)return x>r.x;
    return strcmp(s,r.s)<0;
  }
};
S chara[100000];
int n,m,k,l;

vector<S> like, dislike;
ll calc(int m){
  ll need=0;
  if(dislike.size()<k-m+1)return 0;
  rep(i,m){
    //cerr<<"hoge: "<<dislike[k-m].x-like[i].x<<endl;
    need+=max(0,dislike[k-m].x-like[i].x+
    (strcmp(dislike[k-m].s,like[i].s)<0));
  }
  //cerr<<"m: "<<m<<" need: "<<need<<endl;
  return need;
}

int main(){
  while(scanf("%d%d%d%d",&n,&m,&k,&l),n){
    set<string> names;
    rep(i,n)scanf("%s%d",chara[i].s,&chara[i].x);
    rep(i,m){
      char in[11]; scanf("%s",in);
      names.insert(string(in));
    }
    like.clear(); dislike.clear();
    rep(i,n){
      if(names.count(chara[i].s))like.pb(chara[i]);
      else dislike.pb(chara[i]);
    }
    sort(all(like)); sort(all(dislike));
    //rep(i,dislike.size())cerr<<dislike[i].s<<" "<<dislike[i].x<<endl;
    
    int lo=0, hi=min(m,k)+1, mid;
    while(lo+1<hi){
      mid=(lo+hi)/2;
      if(calc(mid)<=l)lo=mid; else hi=mid;
    }
    printf("%d\n",lo);
  }
  return 0;
}