Post 39

Veröffentlicht am

这两天由于种种缘故没能写Post，主要是因为surface book充电线被我妈忘在家里结果我就什么都干不了。

今天终于拿过来了，这笔记本倒是挺高配，不过我去郑州培训估计也舍不得。

讲真不怎么想去郑州，估计是个坑钱的培训，要不是看有lyd这种讲师我是肯定不会去的。

唯一值得高兴的是终于有个笔记本了。

dessert

甜品囤积者（1）

时间限制：1秒，内存限制：128MB 读入文件名：dessert.in 输出文件名：dessert.out

【题目描述】

放假在家，甜品总是少不了的。

最近你已经瞄中了一家甜品店的甜品，打算接下来连续n天都要吃那里的甜品了。你已经知道了甜品店每天的甜品价格，第i天每袋甜品的价格是ai。而你也计划好了每天要吃的甜品袋数，第i天要吃si袋甜品。

每天你都可以买任意多袋甜品，吃不完可以囤积着并不用担心过期变质，那么为了满足n天的甜品需求，你至少要花费多少钱呢。

【输入格式】

输入共3行。

第一行输入一个正整数n，表示天数。

第二行输入n个正整数，表示第1天到第n天的甜品价格ai，输入用一个空格分隔。

第三行输入n个正整数，表示第1天到第n天计划要吃的甜品袋数si，输入用一个空格分隔。

【输出格式】

输出共一行，包含一个整数，表示最小花费。

【输入输出样例1】

dessert.in

5

3 5 7 1 6

5 9 1 1 10

dessert.out

56

【输入输出样例2】

dessert.in

5

3 10 8 3 10

9 5 8 4 7

dessert.out

99

【输入输出样例3】

dessert.in

5

8 6 5 8 7

10 5 5 1 7

dessert.out

175

【数据规模与约定】

对于前40%的数据，1≤n≤100，1≤ai,si≤1000；

对于前70%的数据，1≤n≤1000；

对于100%的数据，1≤n≤100000，1≤ai,si≤100000。

题解

这道题是一道挺经典的简单贪心。

由于每天买的数量没有限制，所以对于每一天的需求，只需要从他（当然包括这一天）前面最便宜的买好就可以了。程序实现也很简单。不知道为什么做了这么一道水题。

Code：

1
2


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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
int n , f[maxn] , p[maxn] , s[maxn];

struct Deque
{
	int q[maxn] , l , r;
	Deque(){
		l = 1 , r = 0;
	}
	inline void clear(){
		l = 1 , r = 0;
	}
	inline void push(int x){
		q[++r] = x;
	}
	inline void pop_front(){
		q[l++] = 0;
	}
	inline void pop_back(){
		q[r--] = 0;
	}
	inline int front(){
		return q[l];
	}
	inline int back(){
		return q[r];
	}
	inline int size(){
		return r-l+1;
	}
}q;

int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&p[i]);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&s[i]);
	for(int i = 1 ; i <= n ; ++i)
	{
		while(q.size() && p[i] <= p[q.back()]) q.pop_back();
		q.push(i);
		f[i] = p[q.front()];
	}
	long long ans = 0;
	for(int i = 1 ; i <= n ; ++i)
		ans += 1ll * s[i] * f[i];
	printf("%lld\n",ans);
}

今天好像就写了这一道题的程序，不过似乎思考了很多题目只不过今天时间太琐碎就没写。。以后再说说那些有趣的题目吧。

在surface book上搞定了blog，以后就可以用这个了！不过等我的笔记本来了恐怕还得重新配置我的新笔记本。