LOJ刷题 / 2019寒假刷题计划
4 分钟 读完 (大约 674 个字)

10184. 「一本通 5.6 例 1」任务安排 1 & 10185. 「一本通 5.6 例 2」任务安排 2 & 10186. 「一本通 5.6 例 3」任务安排 3


由于这三道题都是同一道题，只是数据范围不同，故拉成同一篇博客

题意

有$n$个任务，机器人($jxc$)会把这$n$个任务分成若干批，从时刻$0$开始，任务将被分批加工，执行第$i$个任务需要花费时间为$T_i$。另外，在每一批任务开始前，机器需要$S$的启动时间。

同一批任务将在同一时刻完成。每个任务的费用$=$它完成的时间$\times$一个费用的系数$C_i$。

思路

对于$n \leq 5000$的数据

时间复杂度$O(N^2)$

设$f[i]​$表示前$i​$个任务所花费最小价值。

初始化：

$$f[i]=inf|1<=i<=n,f[0]=0​$$

转移方程：

$$f[i]=min \left{f[j-1]+S(c[n]-c[j-1])+t[i](c[i]-c[j-1])|1<=j<=i \right}​$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int n,S,f[5010],t[5010],c[5010];
int main(){
	cin>>n>>S;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		t[i]=t[i-1]+x;
		c[i]=c[i-1]+y;
	}
	memset(f,63,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			f[i]=min(f[j-1]+S*(c[n]-c[j-1])+t[i]*(c[i]-c[j-1]),f[i]);
		}
	}
	cout<<f[n]<<endl;
	return 0;
}

对于$1\leq N \leq 10^4$的数据

时间复杂度约为$O(N)$

转移方程同上，
$$f[i]=min \left{ f[j-1]+S(c[n]-c[j-1])+t[i](c[i]-c[j-1])|1<=j<=i \right }​$$

将只含有$i​$的项移出，得：

$$f[i]=min \left { f[j-1]-Sc[j-1]-t[i]c[j-1]|1<=j<=i \right }+Sc[n]+t[i]c[i]​$$

合并同类项，得：

$$f[i]=min \left { f[j]-(S+t[i])c[j]|0<=j<=i-1 \right }+Sc[n]+t[i]*c[i]$$

设$y=f[j]$,$k=S+t[i]$,$x=c[j]$,$b=Sc[n]+t[i]c[i]$

那么：

$$f[i]=y-kx+b$$

即：
$$y=kx+(f[i]-b)$$

  • 斜率优化一：
    因为$t[i]$在递增，斜率$k$在变大，直线越来越陡，所以队首的两个点之间斜率至少要大于$(S+t[i])$。
    即：$(f[q[l+1]]-f[q[l]])/(c[q[l+1]]-c[q[l]])>(S+t[i])$
    即：若$(f[q[l+1]]-f[q[l]])/(c[q[l+1]]-c[q[l]])<=(S+t[i])$，队首弹出
    化简，得：若$(f[q[l+1]]-f[q[l]])<=(S+t[i])*(c[q[l+1]]-c[q[l]])$，队首弹出

  • 斜率优化二：
    确保右侧的斜率大于左侧的斜率，即：$(f[q[r]]-f[q[r-1]])/(c[q[r]]-c[q[r-1]])<(f[i]-f[q[r]])/(c[i]-c[q[r]])​$。
    若$(f[q[r]]-f[q[r-1]])/(c[q[r]]-c[q[r-1]])>=(f[i]-f[q[r]])/(c[i]-c[q[r]])​$,队尾弹出。
    化简，得：若$(f[i]-f[q[r]])(c[q[r]]-c[q[r-1]])<=(f[q[r]]-f[q[r-1]])(c[i]-c[q[r]])​$，队尾弹出 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int n,S,f[300010],t[300010],c[300010],q[300010],l,r;
int main(){
	cin>>n>>S;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		t[i]=t[i-1]+x;
		c[i]=c[i-1]+y;
	}
	memset(f,63,sizeof(f));
	f[0]=0;
	l=1,r=1;
	for(int i=1;i<=n;i++){
		int k=S+t[i];
		while(l<r&&f[q[l+1]]-f[q[l]]<=k*(c[q[l+1]]-c[q[l]])) l++;
		f[i]=f[q[l]]-k*c[q[l]]+t[i]*c[i]+S*c[n];
		while(l<r&&(f[i]-f[q[r]])*(c[q[r]]-c[q[r-1]])<=(f[q[r]]-f[q[r-1]])*(c[i]-c[q[r]])) r--;
		q[++r]=i;
	}
	cout<<f[n]<<endl;
	return 0;
}

对于$1 \leq N \leq 3 \times 10^5 , \left| T_i \right|<2^8$的数据

虽然添加了单调队列的优化，但是时间可以为负数，所以之前维护的单调性就不存在了，所以我们需要使用二分+单调队列来维护斜率。

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
#include<bits/stdc++.h>
using namespace std;
long long n,S,f[300010],t[300010],c[300010],q[300010],l,r,L,R;
long long Cut(long long j){return f[j]-c[n]*t[j]+c[j]*t[j]-c[j]*S;}
int main(){
	cin>>n>>S;
	for(long long i=1;i<=n;i++){
		long long x,y;
		cin>>x>>y;
		t[i]=t[i-1]+x;
		c[i]=c[i-1]+y;
	}
	memset(f,127,sizeof(f));
	f[0]=0;
	L=0,R=0;
	for(long long i=1;i<=n;i++){
		l=0,r=R-1;long long ans=R;
        while(l<=r){
            long long mid=(l+r)>>1;
            if((c[q[mid+1]]-c[q[mid]])*t[i]<=Cut(q[mid+1])-Cut(q[mid])) ans=mid,r=mid-1;
			else l=mid+1;
        }
        long long j=q[ans];
		f[i]=f[j]+(c[n]-c[j])*(t[i]-t[j]+S);
        while(L<R&&(Cut(q[R])-Cut(q[R-1]))*(c[i]-c[q[R]])>=(Cut(i)-Cut(q[R]))*(c[q[R]]-c[q[R-1]])) R--;
		q[++R]=i;
	}
	cout<<f[n]<<endl;
	return 0;
}
LOJ刷题 / 2019寒假刷题计划
3 分钟 读完 (大约 521 个字)

10082. 「一本通 3.3 例 1」Word Rings

题意

每组数据读入一个n和n个字符串。定义前2个与末尾2个字母相同可以连接。问使这个环串的平均长度最大。求这个最大值。不存在输出$No solution$。

思路

平均值公式：
$$
Average=(E_1+E_2+…..+E_n)/n
$$

$$
Average*n=(E_1+E_2+…+E_n)
$$

$$
(E_1-Average)+(E_2-Average)+…+(E_n-Average)=0
$$

那么可以二分答案：
$$
(E_1-Ans)+(E_2-Ans)+…+(E_n-Ans)\geq0
$$
然后瞎搞spfa。

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#define E 200010
#define eps 1e-3
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else{
		write(x/10);
		putchar(x%10+'0');
	}
}
//queue<int> q;
//set<int> s;
//priority_queue<int> q1;
//priority_queue<int,vector<int>,greater<int> > q2;
//list<int> l;
//stack<int> s;
int n;
string str[100010];
int fir[E],nxt[E],son[E],tot,cnt,Max;
double w[E],dis[E],flag;
int vis[E];
int f[6666];
void add(int x,int y,double z){++tot;son[tot]=y;nxt[tot]=fir[x];fir[x]=tot;w[tot]=z;}
void spfa(int s,int v,double mid){
	if(flag==1) return ;
	vis[s]=v;
	for(int i=fir[s];i;i=nxt[i]){
		int to=son[i];
		if(dis[s]+w[i]>dis[to]+mid){
			dis[to]=dis[s]+w[i]-mid;
			if(dis[to]>Max){
				flag=1;
				return ;
			}
			if(!vis[to]) spfa(to,v,mid);
			if(flag) return ;
			else if(vis[to]==v){
				flag=1;
				return ;
			}
		}
	}
	vis[s]=0;
}
bool check(double mid){
	flag=0;
	for(int i=0;i<=cnt;i++) dis[i]=0.0;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=cnt;i++){
		spfa(i,i,mid);
		if(flag==1) break;
	}
	return flag;
}
int main(){
//	freopen("code.in","r",stdin);freopen("code.out","w",stdout);
	n=read();
	while(n!=0){
		for(int i=1;i<=n;i++) cin>>str[i];
		memset(fir,0,sizeof(fir));
		memset(f,0,sizeof(f));
		tot=0;cnt=0;Max=0;
		for(int i=1;i<=n;i++){
			int len=str[i].length();
			Max=max(Max,len);
			int a=(str[i][0]-'a')*26+str[i][1]-'a';
			int b=(str[i][len-2]-'a')*26+str[i][len-1]-'a';
			if(!f[a]) f[a]=++cnt;
			int A=f[a];
			if(!f[b]) f[b]=++cnt;
			int B=f[b];
			add(A,B,(double)len);
		}
		Max*=n;
		double l=0,r=1000,ans=-1,mid;
		while(l+eps<r){
			mid=(l+r)/2;
			if(check(mid)) l=mid,ans=mid;
			else r=mid;
		}
		if(ans!=-1) printf("%.2lf\n",ans);
		else puts("No solution");
		n=read();
	}
	return 0;
}
LOJ刷题 / 2019寒假刷题计划
2 分钟 读完 (大约 353 个字)

10084. 「一本通 3.3 练习 1」最小圈

题意

读入一个有向图，求图中最小环的最小平均值时多少。

思路

当然食用二分+spfa啦。

基本思路同#10082. 「一本通 3.3 例 1」Word Rings

平均值公式：
$$
Average=(E_1+E_2+…..+E_n)/n
$$

$$
Average*n=(E_1+E_2+…+E_n)
$$

$$
(E_1-Average)+(E_2-Average)+…+(E_n-Average)=0
$$

那么可以二分答案：
$$
(E_1-Ans)+(E_2-Ans)+…+(E_n-Ans)\geq0
$$
然后瞎搞spfa。

但这次求最小值。

改一改符号就好了。

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#define E 20010
#define eps 1e-10
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else{
		write(x/10);
		putchar(x%10+'0');
	}
}
//queue<int> q;
//set<int> s;
//priority_queue<int> q1;
//priority_queue<int,vector<int>,greater<int> > q2;
//list<int> l;
//stack<int> s;
int n,m;
int fir[E],nxt[E],son[E],tot;
double w[E],Max;
void add(int x,int y,double z){++tot;nxt[tot]=fir[x];son[tot]=y;fir[x]=tot;w[tot]=z;}
double dis[E],flag;
int vis[E];
int spfa(int s,double mid){
	vis[s]=1;
	for(int i=fir[s];i;i=nxt[i]){
		int to=son[i];
		if(dis[s]+w[i]-mid<dis[to]){
			dis[to]=dis[s]+w[i]-mid;
			if(vis[to]||spfa(to,mid)){vis[s]=0;return 1;}
		}
	}
	vis[s]=0;
	return 0;
}
bool check(double mid){
	for(int i=0;i<=n;i++) dis[i]=0.0;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		if(spfa(i,mid)==1) return 1;
	}
	return 0;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read();double z;
		cin>>z;
		add(x,y,(double)z);
	}
	double l=-1e7,r=1e7,mid,ans;
	while(l+eps<r){
		mid=(l+r)/2;
		if(check(mid)) r=mid-eps,ans=mid;
		else l=mid+eps;
	}
	printf("%.8lf\n",ans);
	return 0;
}
关注我

链接

分类

标签云

Link Cut Tree RMQ Splay bfs dp fhq treap spfa 二分 博弈论 堆 差分 异或 数论 斜率优化 暴力 最长链 枚举 树状数组 树链剖分 模拟 线性筛 线段树 背包 贪心 通知

最新文章

归档

标签

Link Cut Tree 1
RMQ 5
Splay 2
bfs 1
dp 11
fhq treap 1
spfa 9
二分 3
博弈论 1
堆 1
差分 4
异或 1
数论 1
斜率优化 1
暴力 1
最长链 1
枚举 1
树状数组 6
树链剖分 1
模拟 1
线性筛 1
线段树 5
背包 1
贪心 1
通知 1

最新文章

归档

标签

Link Cut Tree 1
RMQ 5
Splay 2
bfs 1
dp 11
fhq treap 1
spfa 9
二分 3
博弈论 1
堆 1
差分 4
异或 1
数论 1
斜率优化 1
暴力 1
最长链 1
枚举 1
树状数组 6
树链剖分 1
模拟 1
线性筛 1
线段树 5
背包 1
贪心 1
通知 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×