uva 11054 - Wine trading in Gergovia

点击打开链接uva 11054

题目意思：    有一个城市，城市里的每一个人都在做酒生意，有的人是要买进用正数表示，有的人是要卖出用负数表示。现在规定这个城市的每家每户都连在一起，还有L升酒的交易代价为“两家的距离xL“，要求我们找到最小的交易代价

解题思路：     1：贪心
                       2：由于每一个人要买的或要卖的物品是一定的，那么我们知道如果要让每一个人的产生最小的交易代价就是让每一个人都和他相邻的人交易，那么这样就有最优解，所以只要从左向右枚举一遍就是O(n)的时间复杂度

代码：

1

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define MAXN 100010

int n;
int bott[MAXN];
long long ans;

void solve() {
    int i;
    ans = 0;
    for(i = 1 ; i < n ; i++){
        bott[i] += bott[i-1];
        ans += abs(bott[i-1]);
    }
    printf("%lld\n" , ans);
}

int main() {
    //freopen("input.txt" , "r" , stdin);
    while(scanf("%d" , &n) && n){
        for(int i = 0 ; i < n ; i++)
            scanf("%d" , &bott[i]);
        solve();
    }
    return 0;
}

2

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define MAXN 100010

int n;
int bott[MAXN];
long long ans;

void solve() {
    int i , j;
    for(i = 0 ; i < n ;){
        if(bott[i] < 0){
            for(j = i+1 ; j < n ; j++){
                if(bott[j] > 0){
                    if(abs(bott[i]) > abs(bott[j])){
                        ans += abs(bott[j])*(j-i);
                        bott[i] += bott[j] ; bott[j] = 0;
                    }
                    else{
                        ans += abs(bott[i])*(j-i);
                        bott[j] += bott[i] ; bott[i] = 0;
                    }
                    break;
                }
            }
        }
        else if(bott[i] > 0){
            for(j = i+1 ; j < n ; j++){
               if(bott[j] < 0){
                    if(abs(bott[i]) > abs(bott[j])){
                        ans += abs(bott[j])*(j-i);
                         bott[i] += bott[j] ; bott[j] = 0;
                    }
                    else{
                        ans += abs(bott[i])*(j-i);
                        bott[j] += bott[i] ; bott[i] = 0;
                    }
                    break;
                }
            }
        }
        if(!bott[i])  i++;
    }
}

int main() {
    //freopen("input.txt" , "r" , stdin);
    while(scanf("%d" , &n) && n){
        for(int i = 0 ; i < n ; i++)
            scanf("%d" , &bott[i]);
        ans = 0 ; solve();
        printf("%lld\n" , ans);
    }
    return 0;
}