題意:
一條街上所有人都以賣酒為生,每一天有的人需要賣掉一些酒而有的人需要買入一些酒;然後在相鄰的人之間運輸一單位的酒需要一單位的花費,問怎麼樣安排人們之間的交易,可以使得總運算費用最小。
思路:
開始就想到一個貪心思路:顯然每個需要買酒的人都應該盡量買他最左邊賣的酒,沒有的話再買他右邊最近賣酒人的酒。第二點很好理解,現在來解釋一下第一點:如果當前這個人不買他最左邊人賣的酒而那些酒反正都是要賣出去的,這些酒就要由他右邊的人買,那麼這些酒賣出的代價就必然變大。
具體實現時我們需要判斷每個人的左邊是不是還有可以買的酒,這樣如果直接通過循環進行判斷的話是一定會超時的(我開始就這樣寫了一次,結果就TL了);實際上我們可以另用一個數組記錄所有賣酒人的坐標,這樣我們每次都只需要掃描這個數組就行了(這個數組開始的元素必定是最左邊買酒人的坐標),如果這個數組前面的項對應的酒量變成0,我們就把開始坐標右移(如果沒有這一步,就肯定會超時)。
但是剛才在網上看到另一種做法,就是不考慮題目中規定的買賣關系,規定第i個人買第i+1個人的酒,這樣答案是對的,但是一下還是想不清楚原理。
代碼如下:
#include#include #include #include using namespace std; #define LL long long int main() { int i,j,k,n,a[110000],b[110000],left; while(scanf("%d",&n)&&n) { LL sum=0; k=0; for(i=0;i 0) { for(j=left;j
另一種方法的代碼:
#include#include #include #include using namespace std; #define LL long long int main() { int i,j,k,n,a[110000],b[110000],left; while(scanf("%d",&n)&&n) { LL sum=0; k=0; for(i=0;i