这道题在比赛的时候一直在想二分答案+贪心判定，结果一直在WA on pretest10……第二天起来一想，发现是有问题的……因为在判定的时候，我是把每一次操作隔离开来看的，但他要求是同时干某件事，所以不能直接给每个人分配k次出手机会。

比如说，现在的分配情况是：

a——b——c

&——_——&

_——&——&

a、c和b、c各一次，如果用之前的策略的话，就还可以用一次a、b，但是，a、b的可用时间是不一样的，所以这是行不通的。

我们现在考虑，一个时间，一个时间地模拟，那么，我们可以模糊地想象出一个贪心的策略。

贪心部分代码：

我们假设a
      
       <= a)    //当最大的
       
        < mx <= b时，a先干掉a能干的，b、c干掉最大的两个。{    sbt.work(a);    sbt.work(b);    sbt.work(c);}else if(mx <= c)//当b <　mx <= c 时，若a和b都可以干掉一个，那么就分别干掉一个，如果a和b只能干掉一个或更少，那么就用a+b去干掉能干掉的最大的，显然更优。c干掉最大的。{    bool flag = true;    int tmp = sbt.Prev(sbt.root, a);    if(tmp != -1)    {        int s1 = tmp;        sbt.erase(sbt.root, tmp);        tmp = sbt.Prev(sbt.root, b);        if(tmp != -1)        {            sbt.erase(sbt.root, tmp);            n -= 2;            sbt.work(c);        }        else        {            sbt.insert(sbt.root, s1);            flag = 0;        }    }    else flag = 0;    if(!flag)    {        int aa = a+b, bb = c;        if(aa > bb) swap(aa, bb);        sbt.work(aa);        sbt.work(bb);    }}// 考虑多个人一起打怪else if(mx <= a + b) // c < mx <= a+b{    int aa = c, bb = a + b;    sbt.work(aa);    sbt.work(bb);}else if(mx <= a + c) // c, a+b < mx <= a + c{    int aa = b, bb = a + c;    sbt.work(aa);    sbt.work(bb);}else if(mx <= c + b) // c, a+b, < a+c < mx <= b + c{    int aa = a, bb = c + b;    sbt.work(aa);    sbt.work(bb);}else{    sbt.work(a+b+c);}
       
      

代码

#include
     
      #include
      
       using namespace std;#define MAXN 200005#define INF 0x3f3f3f3fint n, m, a, b, c, C[3], sd = 2333, sz;int t[MAXN];char ch, f;inline void GET(int &n) {    n = 0; f = 1;    do {ch = getchar(); if(ch == '-') f = -1;} while(ch > '9' || ch < '0');    while(ch >= '0' && ch <= '9') {n=n*10+ch-'0';ch=getchar();}    n *= f;}struct Treap {    struct Node {        int v, s[2], cnt, rnd;    } t[MAXN];    int root;    const inline int Rand() { return sd = sd * sd % 1000007; }    inline void Rot(int &k, bool f) {        int p = t[k].s[f]; t[k].s[f] = t[p].s[f^1];        t[p].s[f^1] = k; k = p;    }    void insert(int &k, int v) {        if(!k) { k = ++ sz; t[k].v = v; t[k].rnd = Rand(); t[k].cnt = 1; return; }        if(t[k].v == v) { ++ t[k].cnt; return; }        bool f = v > t[k].v;        insert(t[k].s[f], v);        if(t[t[k].s[f]].rnd > t[k].rnd) Rot(k, f);    }    void erase(int &k, int v) {        if(!k) return;        if(t[k].v == v) {            if(t[k].cnt > 1) -- t[k].cnt;            else if(t[k].s[0] * t[k].s[1] == 0) k = t[k].s[0] + t[k].s[1];            else {                bool f = t[t[k].s[1]].rnd > t[t[k].s[0]].rnd;                Rot(k, f); erase(k, v);            }            return;        }        bool f = v > t[k].v;        erase(t[k].s[f], v);    }    const int Prev(int k, int v, int p = 200003) {        if(!k) return t[p].v;        else if(t[k].v == v) return v;        else if(t[k].v < v) return Prev(t[k].s[1], v, k);        else return Prev(t[k].s[0], v, p);    }    const bool size() { return root; }    const int Max() {        int tmp = root;        while(t[tmp].s[1]) tmp = t[tmp].s[1];        return t[tmp].v;    }    void work(int val) {        if(!root) return;        int tmp = Prev(root, val);        if(tmp == -1) return;        n --;        erase(root, tmp);    }} sbt;int main() {    scanf("%d", &n); sbt.root = 0; sbt.t[200003].v = -1;    scanf("%d%d%d", &a, &b, &c);    if(a > b) swap(a, b);    if(a > c) swap(a, c);    if(b > c) swap(b, c);    for(int i = 1; i <= n; ++ i) {        GET(t[i]);        sbt.insert(sbt.root, t[i]);    }    if(sbt.Max() > a + b + c) { puts("-1"); return 0; }    int cnt = 0;    for(;sbt.size() && n;) {        ++ cnt;        C[0] = C[1] = C[2] = 0;        int mx = sbt.Max();        if(mx <= a) {            cnt --;            cnt += (n+2)/3;            break;        }        else if(mx <= b) {            sbt.work(a);            sbt.work(b);            sbt.work(c);        }        else if(mx <= c) {            bool flag = true;            int tmp = sbt.Prev(sbt.root, a);            if(tmp != -1) {                int s1 = tmp;                sbt.erase(sbt.root, tmp);                tmp = sbt.Prev(sbt.root, b);                if(tmp != -1) {                    sbt.erase(sbt.root, tmp);                    n -= 2;                    sbt.work(c);                } else {                    sbt.insert(sbt.root, s1);                    flag = 0;                }            } else flag = 0;            if(!flag) {                int aa = a+b, bb = c;                if(aa > bb) swap(aa, bb);                sbt.work(aa);                sbt.work(bb);            }        }        else if(mx <= a + b) {            int aa = c, bb = a + b;            sbt.work(aa);            sbt.work(bb);        }        else if(mx <= a + c) {            int aa = b, bb = a + c;            sbt.work(aa);            sbt.work(bb);        }        else if(mx <= c + b) {            int aa = a, bb = c + b;            sbt.work(aa);            sbt.work(bb);        }        else {            sbt.work(a+b+c);        }    }    printf("%d\n", cnt);    return 0;}