jag2017autumnJ Farm Village

题面

题目链接

翻译

数轴上有 n 个村庄，每个村庄可以生产两个单位的粮食。在每个村庄生产一单位粮食有一定的代价。运输粮食的代价就是运输的距离。求最小代价使得每个村庄都有一个单位的粮食。

题解

虽然在叶老的课件里这题是贪心优化费用流，但是讲起来和写起来和费用流没有毛关系

首先先把问题抽象一下，每个村庄可以有两个出口，需要一个入口，自给自足就可以看作是自己出口给自己，然后

根据一般套路准备两个堆，一个出口一个进口。

————叶老

首先预处理一下，把 d 取前缀和，方便计算距离

那么我们先贪心的想（也就是不计之后的代价），把这一次的出口与之前的入口需求相匹配，如果可以优化答案（也就是他们之间的距离 + \(G_i\)比相匹配的节点自给自足更优），那么就直接使用

然后就有反悔操作，就是更加后面的节点的出口，匹配前面我们匹配上的这个节点，所以每当我们根据贪心取完一次后（贪心每次是从入口堆里取最小值与当前的出口相匹配），就再往入口堆里面丢一个\(-(当前给答案的贡献) - dist[i] + g[i]\)，方便之后反悔（说实话只有这里有点像网络流）

然后还有一个反悔就是这一次的出口不给之前的，给之后的，那么就往出口堆里丢一个\(-(给答案造成的贡献) - dist[i] + g[i]\)，以便之后反悔

做完上述的发现自己的入口需求还没有解决，那么就从出口堆里取出一个最优的，与自己匹配

然后再往入口堆里丢一个\(-(对答案造成的贡献) - dist[j]\)以便之后反悔（用后面的出口来满足自己的入口）

代码

/**************************

  * Author : Leo101

  * Problem : Farm Village

  * Tags : 贪心

**************************/

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <functional>

#define _FILE(s) freopen(#s".in", "r", stdin); freopen(#s".out", "w", stdout)

#define gi get_int()

typedef long long LL;

#define int LL

const int MAXN = 200010;

int get_int()

{

	int x = 0, y = 1; char ch = getchar();

	while (!isdigit(ch) && ch != '-') ch = getchar();

	if (ch == '-') y = -1, ch = getchar();

	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();

	return x * y;

}

int heap1[MAXN], heap2[MAXN], dist[MAXN], cnt1, cnt2;

int topHeap(int* heap, int &cnt)

{

	return heap[0];

}

int deleteHeap(int* heap, int &cnt)

{

	std :: pop_heap(heap, heap + cnt, std :: greater<int>());

	return heap[--cnt];

}

void insertHeap(int* heap, int val, int &cnt)

{

	heap[cnt++] = val;

	std :: push_heap(heap, heap + cnt, std :: greater<int>());

}

signed main()

{

	_FILE(code);

	int n = gi, ans = 0;

	for (int i = 1; i < n; i++) dist[i] = gi + dist[i - 1];

	for (int i = 0; i < n; i++) {

		int cost = gi;

		for (int j = 0; j < 2; j++) {

			int tmp = topHeap(heap1, cnt1) + dist[i] + cost;

			if (cnt1 != 0 && tmp < 0) {

				deleteHeap(heap1, cnt1); ans += tmp;

				insertHeap(heap1, -dist[i] - cost, cnt1);

				insertHeap(heap2, -dist[i] + cost - tmp, cnt2);

			} else {

				insertHeap(heap2, -dist[i] + cost, cnt2);

			}

		}

		int tmp = deleteHeap(heap2, cnt2) + dist[i];

		ans += tmp;

		insertHeap(heap1, -tmp - dist[i], cnt1);

	}

	printf("%lld\n", ans);

	return 0;

}

巴特西

leo101

jag2017autumnJ Farm Village

题面

翻译

题解

代码

最新文章

热门文章