题目描述
NOIP 2012 提高组 题3小 A 和小 B 决定利用假期外出旅行,他们将想去的城市从 1 到 N 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 i 的海拔高度为Hi ,城市 i 和城市 j 之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值,即d[i, j] = |H i ? Hj |。
旅行过程中,小 A 和小 B 轮流开车,第一天小 A 开车,之后每天轮换一次。他们计划
选择一个城市 S 作为起点,一直向东行驶,并且最多行驶 X 公里就结束旅行。小 A 和小 B的驾驶风格不同,小 B 总是沿着前进方向选择一个最近的城市作为目的地,而小 A 总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出 X 公里,他们就会结束旅行。
在启程之前,小 A 想知道两个问题:
1.对于一个给定的 X=X0,从哪一个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小(如果小 B 的行驶路程为 0,此时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小,则输出海拔最高的那个城市。
2. 对任意给定的 X=Xi 和出发城市 Si,小 A 开车行驶的路程总数以及小 B 行驶的路程总数。
输入格式
第一行包含一个整数 N,表示城市的数目。
第二行有 N 个整数,每两个整数之间用一个空格隔开,依次表示城市 1 到城市 N 的海拔高度,即 H1,H2,......,Hn,且每个 Hi 都是不同的。
第三行包含一个整数 X0。
第四行为一个整数 M,表示给定 M 组 Si 和 Xi。
接下来的 M 行,每行包含 2 个整数 Si 和 Xi,表示从城市 Si 出发,最多行驶 Xi 公里。
输出格式
输出共 M+1 行。
第一行包含一个整数 S0,表示对于给定的 X0,从编号为 S0 的城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小。
接下来的 M 行,每行包含 2 个整数,之间用一个空格隔开,依次表示在给定的 Si 和Xi 下小 A 行驶的里程总数和小 B 行驶的里程总数。
【输入样例 1】
4
2 3 4 1
3
4
1 3
2 3
3 3
4 3
【输入样例 2】
10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7
【输出样例 1】
1 1
2 0
0 0
0 0
【输出样例 2】
2
3 2
2 4
2 1
2 4
5 1
5 1
2 1
2 0
0 0
0 0
开始想法：
预处理距离每个城市最近的城市、次近的城市
一步一步模拟A、B的开车路线
时间复杂度：O（n^2）然后考虑倍增
f[i][j]表示从i开始，a、b各开2^j到达的点
同时记录行驶的距离dis[i][j],表示从i开始到达f[i][j]行驶的距离然后复杂度可以优化到log(n)（最后时间不够了然后就没写，惨
这里a开一次b开一次作为1次，所以跳完f[i][j]后
还需另外判断a是否还能在开一次
因为还要a、b各自行驶的距离
所以还要预处理a[i][j],b[i][j],ad[i][j],bd[i][j] （ad意为a的路程，bd同
回到问题第一步，找出与每个城市相隔最近、次近的城市，n^2的找显然不行
用双向链表（然而考试时太麻烦就没写，逃
把城市按高度排序，然后最近的和次近的只会是
前一个or前一个的前一个or后一个or后一个的后一个
因为他只能往东跑所以从最西边的城市开始，每处理完一个城市就把它删掉
所以双向链表（注意第一问要开long double）
ac代码：
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn = ;
const int INF = 0x7fffffff;
struct node{
int id,h,t1,t2;
bool operator < (const node&a)const {
return h<a.h;
}
}peo[maxn];int n,rank[maxn];
int a[maxn][],b[maxn][],f[maxn][];LL ad[maxn][],bd[maxn][],dis[maxn][];
void make_st() {
for(int i=;i<=;i++)
for(int j=;j<=n;j++) {
a[j][i]=a[b[a[j][i-]][]][i-];
b[j][i]=b[a[b[j][i-]][]][i-];
if(a[j][i])ad[j][i]=ad[j][i-]+ad[b[a[j][i-]][]][i-];
if(b[j][i])bd[j][i]=bd[j][i-]+bd[a[b[j][i-]][]][i-];
}
for(int i=;i<=n;i++) {
f[i][]=b[a[i][]][];
dis[i][]=f[i][]?ad[i][]+bd[a[i][]][]:;
}
for(int j=;j<=;j++)
for(int i=;i<n;i++) {
f[i][j]=f[f[i][j-]][j-];
dis[i][j]=f[i][j]?dis[i][j-]+dis[f[i][j-]][j-]:;
}
}
void solve1() {
LL sum=,suma=,sumb=;
long double T=,tmp;
int ans,k;
int S;scanf("%d",&S);
for(int i=;i<n;i++) {
k=i;
suma=sumb=sum=;
for(int j=;j>=;j--) {
if(dis[k][j]&&sum+dis[k][j]<=S) {
sum+=dis[k][j];
suma+=ad[k][j];
sumb+=bd[a[k][]][j];
k=f[k][j];
}
}
if(ad[k][]&&sum+ad[k][]<=S) {
sum+=ad[k][];
suma+=ad[k][];
}
if(!sumb) continue;
tmp=(long double)suma/sumb;
if(T>tmp) {
T=tmp;
ans=i;
}
}
printf("%d\n",ans);
return ;
}
void solve2() {
int m;scanf("%d",&m);
for(int k,s,i=;i<=m;i++) {
scanf("%d%d",&k,&s);
int sum=,suma=,sumb=;
for(int j=;j>=;j--) {
if(dis[k][j]&&sum+dis[k][j]<=s) {
sum+=dis[k][j];
suma+=ad[k][j];
sumb+=bd[a[k][]][j];
k=f[k][j];
}
}
if(ad[k][]&&sum+ad[k][]<=s)
{
sum+=ad[k][];
suma+=ad[k][];
}
printf("%lld %lld\n",suma,sumb);
}
}
int main () {
scanf("%d",&n);
for(int i=;i<=n;++i) scanf("%d",&peo[i].h),peo[i].id=i;
sort(peo+,peo+n+);
for(int i=;i<=n;i++)peo[i].t1=i-,peo[i].t2=i+,rank[peo[i].id]=i;
peo[n].t2=;peo[].h=-;
for(int hx,hxx,hy,hyy,i=;i<n;++i) {
peo[].t1=peo[].t2=;
int pos=rank[i],tmp=peo[pos].h;
int x=peo[peo[pos].t1].id,y=peo[peo[pos].t2].id;
int xx=peo[peo[rank[x]].t1].id,yy=peo[peo[rank[y]].t2].id;
if(x) hx=tmp-peo[rank[x]].h; else hx=INF;
if(xx) hxx=tmp-peo[rank[xx]].h; else hxx=INF;
if(y) hy=peo[rank[y]].h-tmp; else hy=INF;
if(yy) hyy=abs(peo[rank[yy]].h-tmp); else hyy=INF;
if(hx==hy) {
b[i][]=x;a[i][]=y;
if(x)bd[i][]=hx;if(y)ad[i][]=hy;
}
else if(hx<hy) {
b[i][]=x;if(x)bd[i][]=hx;
if(hxx<=hy) a[i][]=xx,ad[i][]=xx?hxx:;
else a[i][]=y,ad[i][]=y?hy:;
}
else {
b[i][]=y;if(y)bd[i][]=hy;
if(hyy<hx) {
a[i][]=yy;if(yy)ad[i][]=hyy;
}
else {
a[i][]=x;if(x)ad[i][]=hx;
}
}
peo[peo[pos].t1].t2=peo[pos].t2;
peo[peo[pos].t2].t1=peo[pos].t1;
}
make_st();
solve1();
solve2();
return ;
}
70分暴力
luogu炸了以后再帖吧