打卡第四天 P1081 [NOIP2012 提高组] 开车旅行

今天是我打卡第四天，做个省选/NOI−题吧(#^.^#)

原题链接：[NOIP2012 提高组] 开车旅行 - 洛谷

题目描述

输入格式 

输出格式 

输入输出样例

输入 #1

4 
2 3 1 4 
3 
4 
1 3 
2 3 
3 3 
4 3

输出 #1

1 
1 1 
2 0 
0 0 
0 0 

输入 #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

输出 #2

2 
3 2 
2 4 
2 1 
2 4 
5 1 
5 1 
2 1 
2 0 
0 0 
0 0

说明/提示

【样例1说明】

 【样例2说明】

【数据范围与约定】

C++

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+100,INF=2e9;
int da[20][N][5],db[20][N][5],f[20][N][5],h[N],s[N],x[N],n,x0,m,la,lb,ansid;
double ans=INF*1.0;
struct City{int id,h;friend bool operator <(City a,City b){return a.h<b.h;}
};
multiset<City> q;
void init(){h[0]=INF,h[n+1]=-INF;City start;start.id=0,start.h=INF;q.insert(start),q.insert(start);start.id=n+1,start.h=-INF;q.insert(start),q.insert(start);for(int i=n;i;i--){City now;now.id=i;now.h=h[i];q.insert(now);auto it=q.lower_bound(now);it--;int lastd=(*it).id,	lasth=(*it).h;it++;it++; int nextd=(*it).id,nexth=(*it).h;it--;int ga,gb;if(abs(nexth-h[i])>=abs(lasth-h[i])){gb=lastd;it--,it--;if(abs(nexth-h[i])>=abs((*it).h-h[i])){ga=(*it).id;} else {ga=nextd;}} else {gb=nextd;it++,it++;if(abs((*it).h-h[i])>=abs(lasth-h[i])){ga=lastd;}else {ga=(*it).id;} }f[0][i][0]=ga,f[0][i][1]=gb;da[0][i][0]=abs(h[i]-h[ga]);db[0][i][1]=abs(h[i]-h[gb]);}
}void fun_dp()  
{for(int i=1;i<=18;i++)for(int j=1;j<=n;j++)for(int k=0;k<2;k++){if(i==1)f[1][j][k]=f[0][f[0][j][k]][1-k],da[1][j][k]=da[0][j][k]+da[0][f[0][j][k]][1-k],db[1][j][k]=db[0][j][k]+db[0][f[0][j][k]][1-k];else f[i][j][k]=f[i-1][f[i-1][j][k]][k],da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][k],db[i][j][k]=db[i-1][j][k]+db[i-1][f[i-1][j][k]][k];}
}void calc(int s,int x){int p=s;la=0,lb=0;for(int i=18;i>=0;i--)if(f[i][p][0]&&la+lb+da[i][p][0]+db[i][p][0]<=x)la+=da[i][p][0],lb+=db[i][p][0],p=f[i][p][0];
} 
void ans1(){for(int i=1;i<=n;i++){calc(i,x0);  double lla=(double)la/(double)lb;if(lla<ans){ans=lla;ansid=i;}else if(lla==ans)if(h[i]>h[ansid])ansid=i;} cout<<ansid<<endl;
}
void ans2(){for(int i=1;i<=m;i++){calc(s[i],x[i]);printf("%d %d\n",la,lb);}
}
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>h[i];cin>>x0>>m;for(int i=1;i<=m;i++)cin>>s[i]>>x[i];init();fun_dp();ans1();ans2();return 0;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Main {public static int MAXN = 100001;public static int MAXP = 20;public static int[] arr = new int[MAXN];public static int[] to1 = new int[MAXN];public static int[] dist1 = new int[MAXN];public static int[] to2 = new int[MAXN];public static int[] dist2 = new int[MAXN];public static int[][] rank = new int[MAXN][2];public static int[] last = new int[MAXN];public static int[] next = new int[MAXN];public static int[][] stto = new int[MAXN][MAXP + 1];public static int[][] stab = new int[MAXN][MAXP + 1];public static int[][] sta = new int[MAXN][MAXP + 1];public static int[][] stb = new int[MAXN][MAXP + 1];public static int n, m, x0;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();n = (int) in.nval;for (int i = 1; i <= n; i++) {in.nextToken();arr[i] = (int) in.nval;}near();st();in.nextToken();x0 = (int) in.nval;out.println(best());in.nextToken();m = (int) in.nval;for (int i = 1, s, x; i <= m; i++) {in.nextToken();s = (int) in.nval;in.nextToken();x = (int) in.nval;travel(s, x);out.println(a + " " + b);}out.flush();out.close();br.close();}public static void near() {for (int i = 1; i <= n; i++) {rank[i][0] = i;rank[i][1] = arr[i];}Arrays.sort(rank, 1, n + 1, (a, b) -> a[1] - b[1]);for (int i = 1; i <= n; i++) {last[rank[i][0]] = i == 1 ? 0 : rank[i - 1][0];next[rank[i][0]] = i == n ? 0 : rank[i + 1][0];}for (int i = 1; i <= n; i++) {to1[i] = 0;dist1[i] = 0;to2[i] = 0;dist2[i] = 0;update(i, last[i]);update(i, last[last[i]]);update(i, next[i]);update(i, next[next[i]]);delete(i);}}public static void update(int i, int r) {if (r == 0) {return;}int d = Math.abs(arr[i] - arr[r]);if (to1[i] == 0 || d < dist1[i] || (d == dist1[i] && arr[r] < arr[to1[i]])) {to2[i] = to1[i];dist2[i] = dist1[i];to1[i] = r;dist1[i] = d;} else if (to2[i] == 0 || d < dist2[i] || (d == dist2[i] && arr[r] < arr[to2[i]])) {to2[i] = r;dist2[i] = d;}}public static void delete(int i) {int l = last[i];int r = next[i];if (l != 0) {next[l] = r;}if (r != 0) {last[r] = l;}}public static void st() {for (int i = 1; i <= n; i++) {stto[i][0] = to1[to2[i]];stab[i][0] = dist2[i] + dist1[to2[i]];sta[i][0] = dist2[i];stb[i][0] = dist1[to2[i]];}for (int p = 1; p <= MAXP; p++) {for (int i = 1; i <= n; i++) {stto[i][p] = stto[stto[i][p - 1]][p - 1];if (stto[i][p] != 0) {stab[i][p] = stab[i][p - 1] + stab[stto[i][p - 1]][p - 1];sta[i][p] = sta[i][p - 1] + sta[stto[i][p - 1]][p - 1];stb[i][p] = stb[i][p - 1] + stb[stto[i][p - 1]][p - 1];}}}}public static int best() {int ans = 0;double min = Double.MAX_VALUE, cur;for (int i = 1; i < n; i++) {travel(i, x0);cur = (double) a / (double) b;if (ans == 0 || cur < min || (cur == min && arr[i] > arr[ans])) {min = cur;ans = i;}}return ans;}public static int a, b;public static void travel(int s, int x) {a = 0;b = 0;for (int p = MAXP; p >= 0; p--) {if (stab[s][p] != 0 && x >= stab[s][p]) {x -= stab[s][p];a += sta[s][p];b += stb[s][p];s = stto[s][p];}}if (dist2[s] <= x) {a += dist2[s];}}}

Pascal

typear=array[1..3]of int64;
varh,down1,down2,z,zz,l,r:array[0..100000]of longint;f:array[1..100000,1..20]of ar;n,m,i,j,x0,a,b:longint;x:ar;
function edge(x,y:longint):longint;
beginexit(abs(h[x]-h[y]));
end;
function jump(x,y:longint):ar;
vari:longint;
beginfillchar(jump,sizeof(jump),0);jump[3]:=x;for i:=20 downto 1 doif(f[jump[3],i,3]>0)and(f[jump[3],i,1]+f[jump[3],i,2]+jump[1]+jump[2]<=y)thenbegininc(jump[1],f[jump[3],i,1]);inc(jump[2],f[jump[3],i,2]);jump[3]:=f[jump[3],i,3];end;if f[jump[3],1,1]+jump[1]+jump[2]<=y thenbegininc(jump[1],f[jump[3],1,1]);jump[3]:=down2[jump[3]];end;
end;
procedure kp(l,r:longint);
vari,j,k,t:longint;
begini:=l;j:=r;k:=h[z[(l+r)div 2]];repeatwhile h[z[i]]<k doinc(i);while h[z[j]]>k dodec(j);if i<=j thenbegint:=z[i];z[i]:=z[j];z[j]:=t;inc(i);dec(j);end;until i>j;if i<r thenkp(i,r);if j>l thenkp(l,j);
end;
procedure build(x:longint);
varll,rr:longint;
beginll:=x;rr:=x;while(ll>0)and(ll<=x)doll:=l[ll];while(rr<n)and(rr<=x)dorr:=r[rr];if ll=0 thendown1[x]:=rrelseif rr>n thendown1[x]:=llelseif edge(x,ll)<=edge(x,rr) thendown1[x]:=llelsedown1[x]:=rr;r[ll]:=rr;l[rr]:=ll;if(down1[x]=ll)and(ll>0)thenbeginll:=l[ll];while(ll>0)and(ll<=x)doll:=l[ll];endelseif rr<=n thenbeginrr:=r[rr];while(rr<n)and(rr<=x)dorr:=r[rr];end;if ll=0 then down2[x]:=rrelseif rr>n thendown2[x]:=llelseif edge(x,ll)<=edge(x,rr) thendown2[x]:=llelsedown2[x]:=rr;if(down1[x]<1)or(down1[x]>n)thendown1[x]:=0;if(down2[x]<1)or(down2[x]>n)thendown2[x]:=0;
end;
beginreadln(n);for i:=1 to n doread(h[i]);readln;for i:=0 to n+1 doz[i]:=i;kp(1,n);for i:=1 to n dobeginl[z[i]]:=z[i-1];r[z[i]]:=z[i+1];end;for i:=1 to n dobuild(i);for i:=1 to n doif down2[i]>0 thenbeginf[i,1,1]:=edge(i,down2[i]);f[i,1,3]:=down2[i];if down1[down2[i]]>0 thenbeginf[i,1,2]:=edge(down2[i],down1[down2[i]]);f[i,1,3]:=down1[down2[i]];end;end;for j:=2 to 20 dofor i:=1 to n doif(f[i,j-1,3]>0)and(f[f[i,j-1,3],j-1,3]>0)thenbeginf[i,j,1]:=f[i,j-1,1]+f[f[i,j-1,3],j-1,1];f[i,j,2]:=f[i,j-1,2]+f[f[i,j-1,3],j-1,2];f[i,j,3]:=f[f[i,j-1,3],j-1,3];end;readln(x0);a:=0;b:=0;j:=0;for i:=1 to n dobeginx:=jump(i,x0);if(a=0)and(b=0)thenbeginj:=i;a:=x[1];b:=x[2];endelseif(b=0)and(x[2]=0)and(h[i]>h[j])thenbeginj:=i;a:=x[1];b:=x[2];endelseif(x[2]<>0)and((b=0)or(x[1]/x[2]<a/b))thenbeginj:=i;a:=x[1];b:=x[2];end;end;writeln(j);readln(m);for i:=1 to m dobeginreadln(a,b);x:=jump(a,b);writeln(x[1],' ',x[2]);end;
end.

下一期要我讲什么题？
打在评论区哦，随机挑选一条评论(#^.^#)，看过我的文章之后，能不能用您珍贵的小手手点赞吧，求求┭┮﹏┭┮