poj 2393 Yogurt factory 贪心

缘起

日常浪费生命 poj 2393 Yogurt factory

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
奶牛们有一个工厂用来生产奶酪，接下来的N周时间里，在第i周生产1单元的奶酪需要花费ci，同时它们也有一个储
存室，奶酪放在那永远不会坏，并且可以无限放，每一单元奶酪放在那的价格恒定为每周S。然后奶牛在第i周会交付
顾客Yi的奶酪，让你求最小花费。

【输入】
第一行 N和S， 1 <= N <= 10,000， 1 <= S <= 100
后面每行Ci和Yi ， 1 <= C_i <= 5,000， 0 <= Y_i <= 10,000

【输出】
最小花费

【样例输入】
4 5
88 200
89 400
97 300
91 500

【样例输出】
126900

【hint】
In week 1, produce 200 units of yogurt and deliver all of it. In week 2, produce 700 
units: deliver 400 units while storing 300 units. In week 3, deliver the 300 units 
that were stored. In week 4, produce and deliver 500 units.

贪心. 贪心策略很简单——反过来想这个问题——就是客户第i周需要的Yi的奶酪应该在第几周(显然<=i)生产?

那么其实就是求{C1+(i-1)*S, C2+(i-2)*S,…,C_{i-1}+S,Ci} 之间的最小值即可. 然后将这个最小值乘以Yi就得到了”为了提供这Yi分量的奶酪而需要付出的花费”, 然后求和即可. 但是n达到了1w, 像刚刚这样做的复杂度显然是O(n^2)的. 一定会被T，正确的做法是用堆维护这个最小值. 等等? 怎么维护呢? 因为每次求最小值的时候堆里面的数字都要变化呀? 这里比较tricky——我们可以让加入的数字变化，即每次加入Ci的时候让Ci-(i-1)*S 即可.

然后求出的最小值加上(i-1)*S 即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
//#define LOCAL
typedef long long LL;

LL n,s,c[10005],y[10005];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%lld%lld", &n,&s);
	for (LL i = 1; i<=n;i++)
	{
		scanf("%lld%lld", c+i, y+i);
	}
	priority_queue<LL, vector<LL>, greater<LL> > pq; // 小根堆
	LL ans = 0;
	for (int i = 1; i<=n;i++)
	{
		pq.push(c[i]-(i-1)*s);
		LL top = pq.top();
		ans+=(top+(i-1)*s)*y[i];
	}
	printf("%lld\n", ans);
	return 0;
}

ac情况

Status Accepted
Time 63ms
Memory 444kB
Length 578
Lang C++
Submitted 2019-08-24 16:50:53
Shared
RemoteRunId 20796210