NOIP2012 开车旅行

拿到这道题应该很容易想到排序。关键是如何处理排序之后原序中只能往右走这个信息。

考虑这样做，在排序好的数组中，离一个点i最近和次进的一定在i-1,i-2,i+1,i+2中。只用处理这四个即可。问题是如何使序合法。

有一种优雅的解法是在排好序的数组中找到原序为1的点，处理好离他最近和次近的点。这样处理出的一定是合法的，因为数组中不存在比它还左的点。处理完后删掉这个点，这样第二个点就变成数组中最左的点了，对他处理出的解也一定是合法的。

关于删掉点这个操作可以用双向链表来实现。

考虑到元素没有重复的，也可以用set来实现。

注意边界问题。（对于set，begin是在set中的，end是不在的，stl中很多区间都是左闭右开的）

预处理完成后，我们现在已知任意一个点当A或B行驶时唯一会去的地方。这构成两条链。

容易想到的一种简化方法是找循环节。我们可以把A行驶一次+B行驶一次打包成一个整体。

想到这一步就已经可以开始打暴力了。需要注意的一个细节是在AB整体不能走后还要判断一次A能不能走。

考虑怎么进行优化。由于是多次询问，我们浪费的时间主要在处理多次询问上，许多点的搜索是进行了多次的。类似求lca，应该想到可以用倍增来维护，大大降低时间复杂度。

注意，倍增的基本单位是AB整体。

初始化时定义以下倍增数组：

1
2
3
for (int i=1;i<=n;i++)f[i][0] = aa[bb[i]]; //f[i][j]表示从点i走2^j个循环节到的点
for (int i=1;i<=n;i++)if(bb[i])b[i][0] = abs(h[bb[i]]-h[i]);//b[i][j]表示b从点i走2^j个循环节走的路程
for (int i=1;i<=n;i++)if(aa[i])a[i][0] = abs(h[bb[i]]-h[aa[bb[i]]]);//a[i][j]表示a从点i走2^j个循环节走的路程

转移方程如下

1
2
3
4
5
6
for (int j=1;j<=19;j++)
	for (int i=1;i<=n;i++){
		f[i][j] = f[f[i][j-1]][j-1];
		a[i][j] = a[i][j-1] + a[f[i][j-1]][j-1];
		b[i][j] = b[i][j-1] + b[f[i][j-1]][j-1];
	}

完整代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;

struct node{
	int h,id;
	node(int a=0,int b=0){
		id = a;h = b;
	}
	bool operator <(const node x) const{
	    return h<x.h;
	}
};

set<node> s;
set<node> ::iterator iter;
node city[maxn];
int jl1,jl2;
int n;
int h[maxn];
int a[maxn][20],b[maxn][20],f[maxn][20];
int aa[maxn],bb[maxn];
map <int,int> ys;
int x0;

pair <int,int> tmp[7];
bool cmp(pair<int,int> a,pair<int,int> b){
	if(a.first==b.first)return a.second<b.second;
	return a.first<b.first;
}

//b先行动. 
void dp(){
	for (int i=1;i<=n;i++)f[i][0] = aa[bb[i]];
	for (int i=1;i<=n;i++)if(bb[i])b[i][0] = abs(h[bb[i]]-h[i]);
	for (int i=1;i<=n;i++)if(aa[i])a[i][0] = abs(h[bb[i]]-h[aa[bb[i]]]);
	for (int j=1;j<=19;j++)
	for (int i=1;i<=n;i++){
		f[i][j] = f[f[i][j-1]][j-1];
		a[i][j] = a[i][j-1] + a[f[i][j-1]][j-1];
		b[i][j] = b[i][j-1] + b[f[i][j-1]][j-1];
	}
}

void run(int s,int x){
	int p=s;
	int x1=x;
	jl1=jl2=0;
	for (int i=19;i>=0;i--){
		if (f[p][i]!=0&&a[p][i]+b[p][i]<=x1){
			x1-=a[p][i]+b[p][i];jl1+=b[p][i];jl2+=a[p][i];p=f[p][i];
		}
	}
	if(bb[p]&&b[p][0]<=x1)jl1+=b[p][0];
}

int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>h[i];
		city[i] = node(i,h[i]);
		s.insert(node(i,h[i]));
		ys[h[i]] = i;
	}
	for (int i=1;i<=n;i++){
		iter = s.find(city[i]);
		int t=0;
		if(iter!=s.begin()){
			iter--;
			tmp[++t] = make_pair(abs((*iter).h-city[i].h),(*iter).
			h);
			if (iter!=s.begin()){
				iter--;
				tmp[++t] = make_pair(abs((*iter).h-city[i].h),(*iter).h);iter++;
			}
			iter++;
		}
		iter++;
		if(iter!=s.end()){
			tmp[++t] = make_pair(abs((*iter).h-city[i].h),(*iter).h);iter++;
			if (iter!=s.end()){
				tmp[++t] = make_pair(abs((*iter).h-city[i].h),(*iter).h);
			}iter--;
		}iter--;
		sort(tmp+1,tmp+t+1,cmp);
		if(t>=1)aa[i]=ys[tmp[1].second];
		if(t>=2)bb[i]=ys[tmp[2].second];
		//for (int i=1;i<=t;i++)cout<<tmp[i].second<<endl;
		//cout<<endl<<endl;
		s.erase(iter);
	}/*
	for (int i=1;i<=n;i++){
		
	}*/
	dp();
	cin>>x0;
	double now=2147483647;
	int ans;
	int p;
	for (int s=1;s<n;s++){
		run(s,x0);
		if(jl2!=0)
		if(double(jl1)/double(jl2)<=now+0.0000001&&double(jl1)/double(jl2)>=now-0.0000001)
			if(h[ans]<h[s])ans=s;
		if(double(jl1)/double(jl2)<now){
			ans=s;now=double(jl1)/double(jl2);
		}
	}
	cout<<ans<<endl;
	int m,s0;
	cin>>m;
	for (int i=1;i<=m;i++){
		cin>>s0>>x0;
		run(s0,x0);
		cout<<jl1<<" "<<jl2<<endl;
	}
	return 0;
}
#OI #图论 #排序 #倍增
NOIP2012 开车旅行
http://example.com/2018/10/20/题目/NOIP2012开车旅行/
作者
robin2333
发布于
2018年10月20日
许可协议