UVA 11054 Wine trading in Gergovia 葡萄酒交易 贪心+模拟
2024-10-21 05:52:18
题意：一题街道上很多酒店，交易葡萄酒，正数为卖出葡萄酒，负数为需要葡萄酒，总需求量和总售出量是相等的，从一家店到另外一家店需要路费（路费=距离×运算量），假设每家店线性排列且相邻两店之间距离都是1,求最小路费。
在纸上模拟了一下，你会发现一家店如果卖酒，它的最终流向就是向两边运送；如果买酒，那它就在那边等别家店送酒过来。（我在废话。。。）
然后第一家店肯定是向右边运酒了，最小的运费当然是卖给右边尽量近的店了，然后第一家店的供求就为0,不需要再考虑了，这样就变成后面几家去买卖的子问题了。
这样是可以解的，但是问题是数据量为10W，而这样解复杂度为O(n^2)，必须超时。
然后可以根据这个思路再模拟一下，你会发现其实酒都是向右移动的，其实，这些各个卖家的酒的移动都可以同时算的：
把第一家的酒交给下一家，路费就是酒×1了；或者把负数的酒交给下一家，表示待会计算下家时有酒了就会反方向运过来，路费也是酒x1。然后继续下一家，由于上一家运费和供求都处理完了，第二家也可以同样处理它的当前供求。
以此类推，模拟一遍就能求出总路费了。
代码：
/*
* Author: illuz <iilluzen@gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: Uva11054.cpp
* Lauguage: C/C++
* Create Date: 2013-08-30 19:41:05
* Descripton: UVA 11054 Wine trading in Gergovia, greed, simutation
*/
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL; int main() {
int n, t, s;
LL cnt;
while (scanf("%d", &n) && n) {
s = cnt = 0;
while (n--) {
scanf("%d", &t);
s += t;
cnt += s > 0 ? s : -s;
}
cout << cnt << endl;
}
return 0;
}
最新文章
- jQuery Mobile 中创建按钮
- js promise 风格编程
- Eighth scrum meeting - 2015/11/2
- 山东省第六届ACM省赛
- LoadRunner中常见参数和变量
- 浅谈C/C++引用和指针的联系和区别
- svn hooks的使用demo
- Swift中switch强大的模式匹配
- Kafka消费者-从Kafka读取数据
- tkinter中spinbox递增和递减控件（十）
- 学python走过的坑 二 element与elements的却别
- 使用Promise发送多个异步请求, 全部完成后再执行
- 2017第八届蓝桥杯C/C++ B组省赛-等差素数列
- FineUI开源版（ASP.Net）初学手册
- 单元测试时 出现找不到类或者 NoClassDefFoundError 的问题
- JavaScript 递归法排列组合二维数组
- python：Non-ASCII character ‘\xe2′ in file
- C# 不使用Task实现的多线程顺序执行
- 正则表达式，regular expression, regex, RE
- 新兵易学，老兵易用----C++（C++11的学习整理---如何减少代码量，加强代码的可读性）