犇:将N头牛叠成犇,每头牛的力气是S_i,体重是W_i,倒下的风险是身上的牛的体重和减去S_i,求最稳定犇的最大risk
平时不学习,昨天期中考试复习到凌晨五点,一整天腾云驾雾一般,晚上A一题醒醒神
事实上,牛的叠放顺序可以确定,并且相当方便。凭感觉,力量越大、体重越大的牛应该放在越下面,否则浪费力气。所以按下面的代码排过序后就是叠放顺序,然后顺序找出最大risk即可。
其实我根本没看出跟二分有什么关系,硬要说的话,似乎可以在搜索最大risk的时候设定一个mid,然后顺序计算risk是否小于mid,不过也太多此一举了吧。
#ifndef ONLINE_JUDGE #pragma warning(disable : 4996) #endif #include <iostream> #include <algorithm> using namespace std; #define MAX_N 50000 + 16 struct Cow { int weight, strength; bool operator < (const Cow& other) const { return other.strength + other.weight < strength + weight; } }; Cow cow[MAX_N]; ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif std::ios::sync_with_stdio(false); std::cin.tie(0); int N; cin >> N; int total = 0; for (int i = 0; i < N; ++i) { cin >> cow[i].weight >> cow[i].strength; total += cow[i].weight; } sort(cow, cow + N); int risk = 0x80808080; for (int i = 0; i < N; ++i) { total -= cow[i].weight; // 减去自己的重量 risk = max(risk, total - cow[i].strength); // 计算risk } cout << risk << endl; #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
12816535 | hankcs | 3045 | Accepted | 644K | 422MS | C++ | 1123B | 2014-04-28 23:58:39 |
如果你知道这题怎么利用二分提高效率,欢迎留言。
知识共享署名-非商业性使用-相同方式共享:码农场 » POJ 3045 Cow Acrobats 题解 《挑战程序设计竞赛》
楼主还在读书吗
算是吧,半工半读
的确用贪心就能解决的题目…二分的效率貌似反而低了