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