题解 P1081 【开车旅行】
Zechariah
2018-09-10 23:57:46
这题建议先把暴力模拟的70分做出来而不是直接打正解，考场上如果想不到用倍增，暴力拿70分也是很可观的
那么先说说暴力思路:
1)预处理
显然我们可以做下面这些事情:
c1[i]表示b在i选择的下一个城市（也就是在i东边距离i最近的城市）
c2[i]表示a在i选择的下一个城市（也就是在i东边距离i第二近的城市）
dist1[i]表示b从i到c1[i]的路程
dist2[i]表示a从i到c2[i]的路程
我们可以从第n-1个城市枚举到第1个城市，在第i+1个城市到第n个城市之间暴力找最近和第二近，具体实现看代码
---
```cpp
for (register int i = n - 1; i >= 1; --i)
{
register ll minn = i + 1, minn2 = 0;
dist1[i] = abs(h[i] - h[i + 1]);
for (register int j = i + 2; j <= n; ++j)
{
if (dist1[i] > abs(h[i] - h[j]) || (dist1[i] == abs(h[i] - h[j]) && h[j] < h[minn]))
{
dist2[i] = dist1[i];
dist1[i] = abs(h[i] - h[j]);
minn2 = minn;
minn = j;
}
else if (dist2[i] == 0 || dist2[i] > abs(h[i] - h[j]) || (dist2[i] == abs(h[i] - h[j]) && h[j] < h[minn2]))
{
dist2[i] = abs(h[i] - h[j]);
minn2 = j;
}
}
c1[i] = minn;
c2[i] = minn2;
}
```
---
2)对于两个问题，分别模拟求解
由于a b是轮流驾驶的，我们可以用一个变量turn记录当前是谁在驾驶，turn为0时a驾驶，为1时b驾驶，然后根据题意记录a b分别走过的路程，判断总路程是否超过限制，模拟即可
得分：70
---
```cpp
#include <bits/stdc++.h>
#define ll long long
#define N 100010
using namespace std;
ll c1[N], c2[N], n, m, h[N] = { INT_MAX }, dist1[N], dist2[N];
inline ll read()
{
register ll num=0;
register char ch;
register bool flag = false;
while ((ch = getchar()) == ' ' || ch == '\n' || ch == '\r');
if (ch == '-')flag = true;else num = ch ^ 48;
while ((ch = getchar()) != ' '&&ch != '\n'&&ch != '\r'&&~ch)
num = num * 10 + (ch ^ 48);
if (flag)return -num; return num;
}
double minv = INT_MAX;
int main()
{
n = read();
for (register int i = 1; i <= n; ++i)h[i] = read();
for (register int i = n - 1; i >= 1; --i)
{
register ll minn = i + 1, minn2 = 0;
dist1[i] = abs(h[i] - h[i + 1]);
for (register int j = i + 2; j <= n; ++j)
{
if (dist1[i] > abs(h[i] - h[j]) || (dist1[i] == abs(h[i] - h[j]) && h[j] < h[minn]))
{
dist2[i] = dist1[i];
dist1[i] = abs(h[i] - h[j]);
minn2 = minn;
minn = j;
}
else if (dist2[i] == 0 || dist2[i] > abs(h[i] - h[j]) || (dist2[i] == abs(h[i] - h[j]) && h[j] < h[minn2]))
{
dist2[i] = abs(h[i] - h[j]);
minn2 = j;
}
}
c1[i] = minn;
c2[i] = minn2;
}
register ll x0 = read(), ans = 0;
for (int i = 1; i <= n; ++i)
{
register ll a = 0, b = 0, loc = i, turn = 0;
while (1)
{
if (turn)
{
if (a + b + dist1[loc] > x0 || !c1[loc])break;
b += dist1[loc];
loc = c1[loc];
}
else
{
if (a + b + dist2[loc] > x0 || !c2[loc])break;
a += dist2[loc];
loc = c2[loc];
}
turn ^= 1;
}
if (!ans || 1.0*a / b - minv < -0.00000001 || (fabs(1.0*a / b - minv) <= 0.00000001&&h[ans] < h[i]))
{
minv = 1.0*a / b;
ans = i;
}
}
printf("%lld\n", ans);
m = read();
while (m--)
{
register ll s = read(), x = read(), a = 0, b = 0, turn = 0;
while (1)
{
if (turn)
{
if (a + b + dist1[s] > x || !c1[s])break;
b += dist1[s];
s = c1[s];
}
else
{
if (a + b + dist2[s] > x || !c2[s])break;
a += dist2[s];
s = c2[s];
}
turn ^= 1;
}
printf("%lld %lld\n", a, b);
}
return 0;
}
```
---
暴力打完了，接下来就是正解了
其实如果直接告诉你正解就是在暴力的基础上用倍增和双向链表优化一下，自己想想，慢慢调也能弄出来，所以还是建议先自己思考一下如何用倍增去优化，然后想想如何用双向链表去初始化
1)这里先说一下为什么用倍增
显然，对于每一个点i，a的选择是唯一的，b的选择也是唯一的，所以不存在最优解，可以用倍增
2)怎么使用双向链表初始化
首先把所有城市的高度和编号存入一个结构体，然后排序，记录一下每个城市排序后的位置。然后这个结构体数组可以直接加一个last域和next域改成双向链表，预处理的时候从1到n在链表上找到对应位置pos[i]，不难想到第一近和第二近一定在pos[i]-2 pos[i]-1 pos[i]+1 pos[i]+2之间，在这四个位置之间和上面的暴力是一样的处理，然后在链表中把pos[i]删去，这样的话由于1到n是从西到东的，链表中除了pos[i]以外的所有城市都在pos[i]东边，那么就可以O(N)预处理出c1 c2 dist1 dist2
3)倍增初始化
下面说说如何初始化倍增以及注意事项
我们定义dist3[i][j]为a和b从i分别开了1<<j次的距离，
dist4[i][j]为a和b从i分别开了1<<j次以后a的总路程，dist5同理，为a和b从i分别开了1<<j次以后b的总路程
c3[i][j]为a和b从i分别开了1<<j次以后他们在什么位置
对于j=0的情况是显然的
---
```cpp
for (register int i = 1; i <= n; ++i)
{
dist4[i][0] = dist2[i];
dist5[i][0] = dist1[c2[i]];
dist3[i][0] = dist2[i] + dist1[c2[i]];
c3[i][0] = c1[c2[i]];
}
```
---
注意一下c1和c2不要弄混了
然后是j>=1的情况
---
```cpp
for (register int j = 1; j <= 20; ++j)
for (register int i = 1; i <= n; ++i)
{
c3[i][j] = c3[c3[i][j - 1]][j - 1];
if (c3[i][j])
{
dist3[i][j] = dist3[i][j - 1] + dist3[c3[i][j - 1]][j - 1];
dist4[i][j] = dist4[i][j - 1] + dist4[c3[i][j - 1]][j - 1];
dist5[i][j] = dist5[i][j - 1] + dist5[c3[i][j - 1]][j - 1];
}
}
```
---
这里需要特别注意的是，j是在外层的，i是在内层的，千万不能搞反了（可能只有我这种蒟蒻会犯这种错），因为要先处理j-1的情形才能处理j，另外，如果c3[i][j]是0，说明不能走了，就不要去处理dist了
然后就初始化完了
4)对问题求解
我们先让a和b一起开，那么用c3和dist3就能得到一个近似最终的情况，最后由于是a先开的，要判断一下a是否可以继续开，因为之前是a开完b也开，可能再开dist3就超过限制而a再开一次并没有超过限制，所以这个判断是必要的，其余的与暴力相似
得分：100
AC代码附上（第二行防作弊）
---
```cpp
#include <bits/stdc++.h>
#define ll long lon
#define N 100010
using namespace std;
ll c1[N], c2[N], c3[N][21], n, m, pos[N], dist1[N], dist2[N], dist3[N][21], dist4[N][21], dist5[N][21];
inline ll read()
{
register ll num = 0;
register char ch;
register bool flag = false;
while ((ch = getchar()) == ' ' || ch == '\n' || ch == '\r');
if (ch == '-')flag = true; else num = ch ^ 48;
while ((ch = getchar()) != ' '&&ch != '\n'&&ch != '\r'&&~ch)
num = num * 10 + (ch ^ 48);
if (flag)return -num; return num;
}
double minv = INT_MAX;
struct Node {
ll h;
int bh, last, next;
}q[N];
inline bool cmp(register Node s, register Node t) { return s.h < t.h; }
inline void updata(register int i, register int loc, register int x)
{
if (x >= 1 && x <= n)
{
if (!dist1[i] || dist1[i] > abs(q[loc].h - q[x].h) || (dist1[i] == abs(q[loc].h - q[x].h) && q[x].h < q[pos[c1[i]]].h))
{
dist2[i] = dist1[i];
dist1[i] = abs(q[loc].h - q[x].h);
c2[i] = c1[i];
c1[i] = q[x].bh;
}
else if (!dist2[i] || dist2[i] > abs(q[loc].h - q[x].h) || (dist2[i] == abs(q[loc].h - q[x].h) && q[x].h < q[pos[c2[i]]].h))
{
dist2[i] = abs(q[loc].h - q[x].h);
c2[i] = q[x].bh;
}
}
}
int main()
{
n = read();
for (register int i = 1; i <= n; ++i)q[i].h = read(), q[i].bh = i;
sort(q + 1, q + n + 1, cmp);
for (register int i = 1; i <= n; ++i)
{
pos[q[i].bh] = i;
if (i != 1)
q[i].last = i - 1;
if (i != n)
q[i].next = i + 1;
}
for (register int i = 1; i <= n; ++i)
{
register int loc = pos[i];
updata(i, loc, q[q[loc].last].last);
updata(i, loc, q[loc].last);
updata(i, loc, q[loc].next);
updata(i, loc, q[q[loc].next].next);
if (q[loc].last)q[q[loc].last].next = q[loc].next;
if (q[loc].next)q[q[loc].next].last = q[loc].last;
q[loc].last = q[loc].next = 0;
}
for (register int i = 1; i <= n; ++i)
{
dist4[i][0] = dist2[i];
dist5[i][0] = dist1[c2[i]];
dist3[i][0] = dist2[i] + dist1[c2[i]];
c3[i][0] = c1[c2[i]];
}
for (register int j = 1; j <= 20; ++j)
for (register int i = 1; i <= n; ++i)
{
c3[i][j] = c3[c3[i][j - 1]][j - 1];
if (c3[i][j])
{
dist3[i][j] = dist3[i][j - 1] + dist3[c3[i][j - 1]][j - 1];
dist4[i][j] = dist4[i][j - 1] + dist4[c3[i][j - 1]][j - 1];
dist5[i][j] = dist5[i][j - 1] + dist5[c3[i][j - 1]][j - 1];
}
}
register ll xx = read(), ans = 0;
for (int i = 1; i <= n; ++i)
{
register ll a = 0, b = 0, loc = i, x0 = xx;
for (register int j = 20; j >= 0; --j)
{
if (dist3[loc][j] && x0 >= dist3[loc][j])
{
x0 -= dist3[loc][j];
a += dist4[loc][j];
b += dist5[loc][j];
loc = c3[loc][j];
}
}
if (dist2[loc] <= x0)a += dist2[loc];
if (a <= 0)continue;
if (!ans || 1.0*a / b - minv < -0.00000001 || (fabs(1.0*a / b - minv) <= 0.00000001&&q[pos[ans]].h < q[pos[i]].h))
{
minv = 1.0*a / b;
ans = i;
}
}
printf("%lld\n", ans);
m = read();
while (m--)
{
register ll s = read(), x = read(), a = 0, b = 0;
for (register int j = 20; j >= 0; --j)
{
if (dist3[s][j] && x >= dist3[s][j])
{
x -= dist3[s][j];
a += dist4[s][j];
b += dist5[s][j];
s = c3[s][j];
}
}
if (dist2[s] <= x)a += dist2[s];
printf("%lld %lld\n", a, b);
}
return 0;
}
```
---