POJ - 3045 Cow Acrobats （二分，或者贪心）

一开始是往二分上去想的，如果risk是x，题目要求则可以转化为一个不等式，S_i + x >= sigma W_j ,j表示安排在i号牛上面的牛的编号。

如果考虑最下面的牛那么就可以写成 S_i + x ≥ sum W - W_i，为了方便处理把i号牛的信息合并到一起 → S_i + W_i + x ≥sum W。

二分x的时候，x是个常量，而从下面往上去安排牛的时候，下面的牛是没有影响决策的，可以看成把W_i去掉。

于是得到一个贪心的选法，把牛按照Si+Wi排序，从下面往上安排牛，可选择的牛应该满足S_i+W_i≥lim W， lim W = sum W - x - sigma Wj, j是在i下面的牛。

因为选择是会改变和号部分，lim W越小后面越容易选到，所以我用优先队列选择满足条件Wi最大的一个。复杂度是O(log(T)*nlogn+nlogn)。

交上去A了以后，看了看别人的runtime，感觉复杂度不对，实际上不用每次选取满足条件Wi最大的一个，因为limW是单减的，当S_i+W_i可选的时候，后面的牛

一定可以选到，所以只要考虑从后往前数是否存在第一个S_i+W_i不可选，如果存在，那么lim W其实和后面的选择顺序是没有关系的。

不用优先队列，复杂度变成了O(logT*n+nlogn)。

最终极的做法应该是贪心了，既然lim W = sum W - x - sigma Wj。sigma Wj的顺序不用考虑，那么只要在不满足条件的时候修改x就好了。

/*********************************************************

*            ------------------                          *

*   author AbyssalFish                                   *

**********************************************************/

#include<cstdio>

#include<iostream>

#include<string>

#include<cstring>

#include<queue>

#include<vector>

#include<stack>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

#include<cmath>

using namespace std;

const int MAX_N = 5e4;

//int W[MAX_N], S[MAX_N];

typedef pair<int,int> pii;

#define WS first

#define W second

int N, sumW;

pii dat[MAX_N];

bool P(int x)

{

    int limW = sumW-x, j = N-;

    while(j >=  && dat[j].WS >= limW){

        limW -= dat[j--].W;

    }

    return j < ;

}

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    scanf("%d",&N);

    int W, S, max_S = ;

    for(int i = ; i < N; i++){

        scanf("%d%d",&W,&S);

        dat[i].WS = W+S;

        max_S = max(max_S, S);

        sumW += dat[i].W = W;

    }

    sort(dat,dat+N);

    int lb = -max_S, ub = sumW;

    while(lb < ub){

        int md = (lb+ub)>>;

        P(md) ? ub = md : lb = md+;

    }

    printf("%d\n",lb);

    return ;

}

巴特西

POJ - 3045 Cow Acrobats （二分，或者贪心）

最新文章

热门文章