poj-3262
贪心 水题
n头牛，每头牛每分钟造成d的破坏，把它赶回牛栏需要t的时间 问按什么顺序去赶牛最终破坏最小
思路：先考虑两头牛的情况，t1，d1和t2，d2 先赶1，破坏：2*t1*d2，先赶2，破坏：2*t2*d1(农夫还要回来所以要乘以2) 所以只需要比较t1*d2和t2*d1的大小就可以判断赶的顺序 比较函数为bool cmp(P a, P b) {return a.t*b.d < b.t*a.t; }
当n>2的时候，这个函数也适用 试想如果赶牛的顺序中有两头牛的顺序不符合上面的方式，那么，我们只要将这两头牛的顺序调换过来，最后的破坏就会小一些，所以必须要所有牛的顺序都符合，最后结果才是最小
还做过另一题类似的，两组数字，每组n个，记作ai,bi 每次从两组数字中各选一个数字，将它们相乘，将所有结果相加，如何的到最大结果 思路也是从n=2的时候开始考虑， 结果是：a1*b1+a2*b2或a1*b2+a2*b1 只需要比较两者大小 将两者相减： a1*b1+a2*b2-a1*b2-a2*b1 = a1*(b1-b2） - a2*(b1-b2) = (a1-a2)*(b1-b2) 显然，要得到最大值，两组数字必须是相通的顺序，从小到大或者从大到小排序 同样的，可以推广到n>=2的时候
注意int会溢出，要用long long
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;typedef long long ll;const int MAXN = 100000 + 100;int n;struct P {int t, d; };bool cmp(const P &a, const P &b){ return a.t*b.d < b.t*a.d;}P p[MAXN];int main(){ while(scanf("%d", &n) == 1) { ll d = 0; for(int i=0; i<n; i++) scanf("%d%d", &p[i].t, &p[i].d), d+= p[i].d; sort(p, p+n, cmp); ll ans = 0; for(int i=0; i<n; i++) { d-=p[i].d; ans+=p[i].t*2*d; } cout << ans << endl; } return 0;}新闻热点
疑难解答
