Post 6

Veröffentlicht am | Edited on

在事情未成功之前，人们总说不可能。

「一本通 5.6 例 2」任务安排 2

题目描述

原题来自：JoyOI TYVJ 1098

有 NN 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 NN 个任务分成若干批，每一批包含连续的若干个任务。从时刻 00 开始，任务被分批加工，执行第i个任务所需的时间是 T_iTi。另外，在每批任务开始前，机器需要 SS 的启动时间，故执行一批任务所需的时间是启动时间 SS 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。也就是说，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 C_iCi。

请为机器规划一个分组方案，使得总费用最小。

输入格式

第一行是 NN。第二行是 SS。

下面 NN 行每行有一对正整数，分别为 T_iTi 和 C_iCi，表示第 ii 个任务单独完成所需的时间是 T_iTi 及其费用系数 C_iCi。

输出格式

一个数，最小的总费用。

样例

样例输入

1
2
3
4
5
6
7
5
1
1 3
3 2
4 3
2 3
1 4

样例输出

1
153

样例说明

分组方案为 \{1,2\},\{3\},\{4,5\}{1,2},{3},{4,5}，则完成时间为 \{5,5,10,14,14\}{5,5,10,14,14}，费用 C=\{15,10,30,42,56\}C={15,10,30,42,56}，总费用为 153153。

数据范围与提示

对于全部数据，

题解

首先根据费用提前计算的思想，可以设

f(i)表示前i项任务分成若干组时的最小值。

将其变形后变为

让后面的部分最小，可以把

的值看成直线上的点，让后面的部分值最小就是截距最小等价于

最小。显然维护下凸壳即可。假如一个点左边线段斜率比给定斜率小，右边比给定斜率大，这个点对于这条直线就是最“凸”的，也就是我们要找的点。

由于直线斜率单增，可以使用单调队列将小于给定斜率的点都弹出，取队头即为最优转移点。

时间复杂度

Code：

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
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 300005
#define LL long long
LL f[maxn] , s[maxn],t[maxn];
int n , T;
struct queue
{
	int p[maxn] , l , r;
	queue(){
		l = 1 , r = 0;
		std::memset(p,0,sizeof(p));
	}
	inline void push_back(int x){
		p[++r] = x;
	}
	inline void pop_front(){
		p[l] = 0 ; ++l;
	}
	inline void pop_back(){
		p[r] = 0 ; --r;
	}
	inline int& operator()(int x){
		return p[l+x-1];
	}
	inline int& operator[](int x){
		return p[r-x+1];
	}
	inline bool empty(){
		return !(l <= r);
	}
	inline int size(){
		return r - l + 1;
	}
	inline void debug(){
		puts("Start debug");
		printf("%d %d\n",p[l],p[r]);
	}
}q;
int main()
{

	scanf("%d%d",&n,&T);
	for(int i = 1 ; i <= n ; ++i)
	{
		int x ,y;
		scanf("%d%d",&x,&y);
		t[i] = t[i-1] + x;
		s[i] = s[i-1] + y;
	}
	q.push_back(0);
	std::memset(f,0x7f,sizeof(f));
	f[0] = 0;
	for(int i = 1 ; i <= n ; ++i)
	{
		while(q.size() > 1 && f[q(2)]-f[q(1)] < (s[q(2)]-s[q(1)]) * (T + t[i]))
			q.pop_front();
		f[i] = f[q(1)] - (T + t[i]) * s[q(1)] + s[i] * t[i] + T * s[n];
		while(q.size() > 1 && (f[i]-f[q[1]])*(s[q[1]]-s[q[2]]) <= (f[q[1]]-f[q[2]])*(s[i]-s[q[1]]))
			q.pop_back();
		q.push_back(i);
	}
	printf("%lld",f[n]);
}

今天做题有点少啊，效率又有待提高。

其实主要原因是上面那题我又调了一天，原因是把变量名打错了。。

GG