SRM582 Div2

midだけ・・・

mid
問題概要：
m人の魔法少女とn体の敵がいる
魔法少女と敵はそれぞれ強さMS[i](i <= m), ES[i](i <=n)をもつ
魔法少女は自分の強さ以下の敵を倒せる
一回の攻撃で倒せる敵は１体のみである
一回攻撃する度に攻撃した魔法少女は疲労が１たまる（初期は疲労０）
魔法少女の中で最大の疲労を最小にしたい
そのような値をもとめよ

解法：
2部探索で疲労の最小値をきめる
最小値を決めることで本当にその値で敵を全て倒せるのかどうか貪欲法で確かめることができるようになる
つまり、強い魔法少から降順に決めた数分だけ敵を倒していって最後まで倒せたらOK
最後まで倒せない or 魔法少女の強さよりも敵の強さのほうが大きいならfalseとできる

コード：

#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <cassert>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <cctype>
#include <climits>
#include <cstdlib>
#include<numeric>
#include <iomanip>
#include <cmath>
#include <set>
#define EPS 1e-10
#define F first
#define S second
#define pb push_back
#define pf push_front
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define INF (1<<28)
#define all(n) n.begin(),n.end()

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<vector<vector<int> > > vvvi;


class SpaceWarDiv2 {
public:

  bool check(vi &ms,vector<ii> vec,int v)
  {
    int vs = vec.size();
    int msize = ms.size();
    int p = vs-1;
    for(int i=msize-1;i>=0;i--)
      {
	int cnt = 0;
	while(vec[p].S > 0 && cnt < v)
	  {
	    if(vec[p].F > ms[i])return false;
	    vec[p].S--;
	    cnt++;
	    if(vec[p].S == 0)p--;
	    if(p < 0)return true;
	  }


      }
    return false;
  }

  int minimalFatigue(vector <int> ms, vector <int> es, vector <int> ec) {
    sort(ms.begin(),ms.end());

    map<int,int> index;
    rep(i,es.size())index[es[i]] += ec[i];
    vector<ii> vec;
    for(map<int,int>::iterator it = index.begin(); it != index.end(); it++)
      vec.push_back(ii(it->first,it->S)); 

    if(vec[vec.size()-1].F > ms[ms.size()-1])return -1;


    int L = 0;
    int R = 100000000;
    int MID;
    for(int i=0;i<100;i++)
      {

	MID = (L+R)/2;
	if(check(ms,vec,MID))R = MID;
	else                 L = MID;

      }

    if(check(ms,vec,L))return L;
    else return R;
  }
};