POJ 2456

题目地址:http://poj.org/problem?id=2456

题目大意

农夫约翰有$N$间牛舍排在一条直线上,第$i$号牛舍在$x_i$的位置,其中有$C$头牛对牛舍不满意,因此经常相互攻击。需要将这$C$头牛放在离其他牛尽可能远的牛舍,也就是求最大化最近两头牛之间的距离。

思路

二分搜索,现将牛舍排序,然后定义c(d),表示可安排的$C$头牛最近距离不小于$d$。

AC代码

/*************************************************************************
    > File Name: 2456.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-21 一 14:53:34 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int N, C; // 牛的总数N,会攻击其他牛的数量C
int x[100004];

bool c(int d) { // 表示可安排的C头牛距离不小于d
    int last = 0; // 从第一个牛舍开始枚举
    for(int i=1; i<C; ++i) { // 对C头牛进行安排
        int crt = last + 1;
        while(crt < N && x[crt] - x[last] < d) ++crt; // 寻找距离大于d的下一个牛舍
        if(crt == N) return false; // 若无法安排C头牛
        last = crt; // 继续安排
    }
    return true; // 能安排C头牛
}

void solve() {
    sort(x, x+N);
    int lb = 0, ub = 1000000006;
    while(ub - lb > 1) {
        int mid = (ub + lb) >> 1;
        if(c(mid)) lb = mid; // 半闭半开区间[lb, ub)
        else ub = mid;
    }
    printf("%d\n", lb);
}

int main()
{
#ifdef Oj
    freopen("2456.in", "r", stdin);
#endif
    scanf("%d%d", &N, &C);
    for(int i=0; i<N; ++i)     scanf("%d", &x[i]);
    solve();
    return 0;
}

POJ 3258

题目地址:http://poj.org/problem?id=3258

题目大意

在长为$L$的河两端有石头,分别为起始石头和终点石头。

河中有$N$块石头,相对于起始石头距离分别为$D_i$,现在需要去掉$M$个石头(除了起始和终点石头),求出最小的石头间距的最大值。

思路

和上一题差不多,只要保留$N-M$块石头,然后二分搜索出最大的最小间距。

注意将起始石头和终点石头都算进去了,方便后面计算距离,以选取保留的石头

AC代码

/*************************************************************************
    > File Name: 3258.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-21 一 15:28:36 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int L, N, M;
int D[50005];

bool C(int d) {
    // 这里从第一块石头开始选取,表示第一块是必须保留的,然而终点石头无需考虑,因为能够保留N-M块石头的话,且间距>=d块的石头,那么最后一块可以随意选择,可看做选择保留最后一块即可。
    int lst = 0; // 从第一个石头开始试
    for(int i=1; i<N-M; ++i) { // 保留N-M个石头
        int crt = lst + 1;
        while(crt < N && D[crt] - D[lst] < d) ++crt; // 选取下一个保留的石头
        if(crt == N) return false; // 没有更多符合间距>=d的石头了
        lst = crt;
    }
    return true; // 能够保留N-M块石头
}

void solve() {
    sort(D, D+N); // 按距离排序
    // for(int i=0; i<N; ++i) printf("%d ", D[i]);
    int lb = 0, ub = 1000000005;
    while(ub - lb > 1) {
        int mid=(lb + ub) >> 1;
        if(C(mid)) lb = mid; // 半闭半开区间[lb, ub)
        else ub = mid;
    }
    printf("%d\n", lb);
}

int main()
{
#ifdef Oj
    freopen("3258.in", "r", stdin);
#endif
    scanf("%d%d%d", &L, &N, &M);
    for(int i=1; i<=N; ++i) scanf("%d", &D[i]);
    // 这里将起始石头和终点石头都算进去了,方便后面计算距离,以选取保留的石头
    D[0] = 0, D[N+1] = L;
    N+=2;
    solve();
    return 0;
}

POJ 3273

题目地址:http://poj.org/problem?id=3273

题目大意

给出$N$个账单,分类成$M$份,使每份账单尽可能小,求出此时的账单最大值。

思路

这个比较奇葩了,算是最小化最大值。。

定义C(int x)表示当<=x刀时最少能分成多少份,用来判断是否满足条件。

AC代码

/*************************************************************************
    > File Name: 3273.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-21 一 16:32:27 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int N, M;
int money[100005];


bool C(int x) { // 当<=x刀时最少能分成多少份,用来判断是否满足条件
    int cnt = 0;
    int sum = 0;
    for(int i=0; i<N; ++i) {
        if(money[i] > x) return false;
        sum += money[i];
        if(sum > x) {
            sum = money[i];
            ++cnt;
        }
    }
    if(sum <= x) ++cnt; // 最后一份

    return cnt <= M; // cnt表示<=x刀时至少能分成的份数,所以只要<=M即可(因为可以从cnt中再分,凑成M份)
}

void solve() {
    int lb = 0, ub = 1<<30;

    // C(600);
    while(ub - lb > 1) {
        int mid = (lb + ub) >> 1;
        // printf("mid: %d\n", mid);
        if(C(mid)) ub = mid; // 半闭半开区间(lb, ub]
        else lb = mid;
    }
    printf("%d\n", ub);
}

int main()
{
#ifdef Oj
    freopen("3273.in", "r", stdin);
#endif
    scanf("%d%d", &N, &M);
    for(int i=0; i<N; ++i)     scanf("%d",&money[i]);
    solve();
    return 0;
}

POJ 3104

题目地址:http://poj.org/problem?id=3104

题目大意

Jane有$N$件衣服要洗,洗完后每件有$a_i$滴水,需要干燥这些衣服。

每分钟衣服上的水都会自然风干减少一滴,若用烘干机烘干,每分钟可烘干$k$滴水(用烘干机的话就不会风干)。并且每次只能烘一件衣服。

求出干燥所有衣服的最少时间。

思路

这题坑比较多,需要注意数据范围。。

还是用二分搜索,定义C(x)表示<=x分钟是否能干燥所有衣服。

将当前衣服水量减去x,若还剩水的话用烘干机烘干,这样可求出最小烘干时间。那么烘干机所需要烘干的时间为$\dfrac{a_i-x}{k-1}$(除以$k-1$,是因为烘干过程中不会自然风干,所以$k-1$,加上前面减去x分钟的某一分钟,$k-1+1=k$可看做在烘干机中烘干而不是风干),将所有烘干时间加起来(此时为最小烘干总时间)若大于x则无法完成。

AC代码

/*************************************************************************
    > File Name: 3104.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-22 二 10:52:13 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
typedef long long ll;

int n;
int a[100000+5], k;
bool C(ll x) { // <=x分钟能否烘干所有衣服
    ll minute = 0; // 烘干机最少烘干的时间
    for(int i=1; i<=n; ++i) {
        int cura = a[i] - x; // 假设总共需要x分钟,那么减去x滴风干的水分,即可求得最少烘干机分钟
        if(cura > 0) minute += ceil(cura*1.0/(k-1)); // 若风干x滴水还剩水的话,用烘干机烘干,统计烘干机时间,除以k-1,是因为烘干过程中不会自然风干,所以k-1,加上前面x分钟的某一分钟,k-1+1=k可看做在烘干机中烘干而不是风干
        if(minute > x) return false; // 若烘干机最少烘干时间都大于总时间的话,即无法完成
    }
    return true;
}

void solve() {
    // cout << C(5) << endl;
    if(k == 1) { // 特殊情况
        printf("%d\n",*max_element(a+1, a+1+n));
        return;
    }

    ll lb = 0, ub = *max_element(a+1, a+1+n);
    while(ub - lb > 1) {
        ll mid = (ub + lb) >> 1;
        if(C(mid)) ub = mid; // 半闭半开区间,(lb, ub]
        else lb = mid;
    }
    printf("%lld\n", ub);
}

int main()
{
#ifdef Oj
    freopen("3104.in", "r", stdin);
#endif
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
    scanf("%d", &k);
    solve();
    return 0;
}

POJ 3045

题目地址:http://poj.org/problem?id=3045

题目大意

一堆牛($N$个)玩叠罗汉游戏,现已知每头牛的重量$W_i$和力量$S_i$,风险系数计算为当前牛顶上所有牛的总重量减去自身力量值。

现问,最稳定情况下最大风险能有多大?(其实就是问所有堆叠情况中最大风险能有多小。)

思路

这题贪心算法吧,先求出最稳定的情况,在求最大风险。

最稳定情况可以这么求,

假设其中有两头牛A, B。体重和力量分别为$W_A, S_A和W_B, S_B$。
那么根据题意,当$W_A - S_B > W_B - S_A$的时候,A应该在下面最稳定(因为此时风险$risk=W_B-S_A$比较小,局部最小取得全局最小),否则A在上面。
所以可以根据$W_A - S_B > W_B - S_A$来排序,这样的堆叠情况求出来的最大风险值即为最小的

AC代码

/*************************************************************************
    > File Name: 3045.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-22 二 17:38:43 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int N;
int Wsum = 0;
struct cow {
    int W, S;
    bool operator<(const cow &b) const {
        return W - b.S > b.W - S; // W-S从大到小排序
    }
} cows[50005];

void solve() {
    sort(cows, cows+N);
    int risk = -1000000002; // 因为risk可能为负数
    for(int i=0; i<N; ++i)
        printf("w:%d s:%d\n", cows[i].W, cows[i].S);

    for(int i=0; i<N; ++i) {
        // printf("%d\n", cows[i].W);
        Wsum -= cows[i].W;
        risk = max(risk, Wsum - cows[i].S);
    }
    cout << risk << endl;
}

int main()
{
#ifdef Oj
    freopen("3045.in", "r", stdin);
#endif
    cin.sync_with_stdio(false);
    cin >> N;
    for(int i=0; i<N; ++i) {
        cin >> cows[i].W >> cows[i].S;
        Wsum += cows[i].W;
    }
    solve();
    return 0;
}