本文主要是介绍poj 3262贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
看的大神的证明：
贪心
> 当前最优,因为每一次搬运之后剩下的问题和原问题一样,只是规模变小了,故如果每次选出当前最优的解来进行选取,则累计起来的解也是最优的. > 所以这是一道贪心题. > 选择策略, > 1 在二个中间选择之中,能根据time/eat小的那个为最优解 > 证明: > 二个羊中 A,B,属性分别为分别为eatA,timeA,eatB,timeB > 选A的时候损失timeA*eatB > 选B的时候损失timeB*eatA > 双方同除以eatA*eatB. > 令time/eat为一个羊的比率x > 可以证明x小的那个为最优解. > > 定理,如果有一个选择在n个选择中是最优的,那么(在包含这个选择的)n-1个选择中也是最优的, > > 逆否命题,如果一个选择在n-1个选择中不是最优的,那么在n个选择中也不是最优的. > > 推论,如果一个选择在2个选择中不是最优的,那么在n个选择中也不是最优的 > > 所以将羊按照比率x排序,可以找到一个羊A在与其它所有羊比较的过程中都是最优的, > > 或者说其它n-1的羊在与别的羊做两个之间选一个的选择的时候不是最优的,所有这n-1个羊不是最优解的. > 所以羊A是n头羊中最优解 > > (这个证明先令x的值都是不同的,对x相同的证明只需要将最优,改成没有更优即可 ^_^ )
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;#define MAX_N 1000000pair <int, int> arr[MAX_N];
pair <double, int> tmp[MAX_N];
int N;int main(){scanf("%d", &N);long long sum = 0,ans = 0;for(int i = 0;i < N; i++){scanf("%d%d", &arr[i].first, &arr[i].second);tmp[i].first = arr[i].first*1.0 / arr[i].second;tmp[i].second = i;}sort(tmp, tmp + N);for(int i = 0;i < N; i++){ans += sum * arr[tmp[i].second].second;sum += arr[tmp[i].second].first * 2; }printf("%lld\n", ans);return 0;
}
这篇关于poj 3262贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
