poj-3262

貪心 水題

n頭牛，每頭牛每分鐘造成d的破壞，把它趕回牛欄需要t的時(shí)間 問按什么順序去趕牛最終破壞最小

思路：先考慮兩頭牛的情況，t1，d1和t2，d2 先趕1，破壞：2*t1*d2，先趕2，破壞：2*t2*d1(農(nóng)夫還要回來所以要乘以2) 所以只需要比較t1*d2和t2*d1的大小就可以判斷趕的順序 比較函數(shù)為bool cmp(P a, P b) {return a.t*b.d < b.t*a.t; }

當(dāng)n>2的時(shí)候，這個(gè)函數(shù)也適用 試想如果趕牛的順序中有兩頭牛的順序不符合上面的方式，那么，我們只要將這兩頭牛的順序調(diào)換過來，最后的破壞就會(huì)小一些，所以必須要所有牛的順序都符合，最后結(jié)果才是最小

還做過另一題類似的，兩組數(shù)字，每組n個(gè)，記作ai,bi 每次從兩組數(shù)字中各選一個(gè)數(shù)字，將它們相乘，將所有結(jié)果相加，如何的到最大結(jié)果 思路也是從n=2的時(shí)候開始考慮， 結(jié)果是：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) 顯然，要得到最大值，兩組數(shù)字必須是相通的順序，從小到大或者從大到小排序 同樣的，可以推廣到n>=2的時(shí)候

注意int會(huì)溢出，要用long long