网址如下：

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做，但是我还不太会