程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva--11054Wine trading in Gergovia +貪心

uva--11054Wine trading in Gergovia +貪心

編輯:C++入門知識

uva--11054Wine trading in Gergovia +貪心


題意:

一條街上所有人都以賣酒為生,每一天有的人需要賣掉一些酒而有的人需要買入一些酒;然後在相鄰的人之間運輸一單位的酒需要一單位的花費,問怎麼樣安排人們之間的交易,可以使得總運算費用最小。

思路:

開始就想到一個貪心思路:顯然每個需要買酒的人都應該盡量買他最左邊賣的酒,沒有的話再買他右邊最近賣酒人的酒。第二點很好理解,現在來解釋一下第一點:如果當前這個人不買他最左邊人賣的酒而那些酒反正都是要賣出去的,這些酒就要由他右邊的人買,那麼這些酒賣出的代價就必然變大。

具體實現時我們需要判斷每個人的左邊是不是還有可以買的酒,這樣如果直接通過循環進行判斷的話是一定會超時的(我開始就這樣寫了一次,結果就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;i0)
             {
                 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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved