P3052 [USACO12MAR] Cows in a Skyscraper G

网址如下：

P3052 [USACO12MAR] Cows in a Skyscraper G - 洛谷

（题意翻译中的wi改成ci）

好久没写博客了，寒假加入校队，高强度刷题，感觉懒得写，寒假前倒是写了一个关于虚拟机共用宿主机的VPN的博客的，结果没过审，只能说对翻墙管的是真严啊

后面寒假了就只顾着爽玩了，没怎么刷题（中途还被我姐拉去写pyhon搞数据，算是增长经验）

关于这道题：

刚开始直接用贪心干的，结果贪心思路有问题，加上使用STL过度，直接TLE+WA了：

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

bool cmp(const int &e, const int &val){return e >= val;}

int main(void)
{
    vector<int> vec;
    int n, w; scanf("%d%d", &n, &w);
    for(int i = 0; i < n; i++){
        int val; scanf("%d", &val);
        vec.push_back(val);
    }
    sort(vec.begin(), vec.end(), cmp);
    int cnt = 0, val = 0;
    while(!vec.empty()){
        auto it = lower_bound(vec.begin(), vec.end(), val, cmp);
        if(it == vec.end()){cnt++; val = w;}
        else{val = val - *it; vec.erase(it);}
    }
    printf("%d", cnt);

    return 0;
}

后面是改成二分查找答案：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 20;
int c[maxn], n, w;
int u[maxn];

bool cmp(const int &e, const int &val){return e >= val;}
bool dfs(int cur, int d){
    if(cur == n) return true;
    for(int i = 0; i < d; i++)
        if(u[i] + c[cur] <= w){
            u[i] += c[cur];
            if(dfs(cur + 1, d)) return true;
            u[i] -= c[cur];
        }
    return false;
}

int main(void)
{
    scanf("%d%d", &n, &w);
    int l = 0, r = n;
    for(int i = 0; i < n; i++){scanf("%d", &c[i]); l += c[i];}
    sort(c, c + n, cmp);
    l = l / w;
    while(l < r){
        int mid = (l + r) >> 1; memset(u, 0, sizeof(u));
        if(dfs(0, mid)) r = mid; else l = mid + 1;
    }
    printf("%d", l);

    return 0;
}

这道题也可以用状压dp做，但是我还不太会