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

时间:2024-10-09 20:38:37

今天是我打卡第四天,做个省选/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

type
        ar=array[1..3]of int64;
var
        h,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;
begin
        exit(abs(h[x]-h[y]));
end;
function jump(x,y:longint):ar;
var
        i:longint;
begin
        fillchar(jump,sizeof(jump),0);
        jump[3]:=x;
        for i:=20 downto 1 do
                if(f[jump[3],i,3]>0)and(f[jump[3],i,1]+f[jump[3],i,2]+jump[1]+jump[2]<=y)then
                begin
                        inc(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 then
        begin
                inc(jump[1],f[jump[3],1,1]);
                jump[3]:=down2[jump[3]];
        end;
end;
procedure kp(l,r:longint);
var
        i,j,k,t:longint;
begin
        i:=l;
        j:=r;
        k:=h[z[(l+r)div 2]];
        repeat
                while h[z[i]]<k do
                        inc(i);
                while h[z[j]]>k do
                        dec(j);
                if i<=j then
                begin
                        t:=z[i];
                        z[i]:=z[j];
                        z[j]:=t;
                        inc(i);
                        dec(j);
                end;
        until i>j;
        if i<r then
                kp(i,r);
        if j>l then
                kp(l,j);
end;
procedure build(x:longint);
var
        ll,rr:longint;
begin
        ll:=x;
        rr:=x;
        while(ll>0)and(ll<=x)do
                ll:=l[ll];
        while(rr<n)and(rr<=x)do
                rr:=r[rr];
        if ll=0 then
                down1[x]:=rr
        else
                if rr>n then
                        down1[x]:=ll
        else
                if edge(x,ll)<=edge(x,rr) then
                        down1[x]:=ll
        else
                down1[x]:=rr;
        r[ll]:=rr;l[rr]:=ll;
        if(down1[x]=ll)and(ll>0)then
        begin
                ll:=l[ll];
                while(ll>0)and(ll<=x)do
                        ll:=l[ll];
        end
        else
                if rr<=n then
                begin
                        rr:=r[rr];
                        while(rr<n)and(rr<=x)do
                                rr:=r[rr];
                end;
        if ll=0 then down2[x]:=rr
        else
                if rr>n then
                        down2[x]:=ll
        else
                if edge(x,ll)<=edge(x,rr) then
                        down2[x]:=ll
        else
                down2[x]:=rr;
        if(down1[x]<1)or(down1[x]>n)then
                down1[x]:=0;
        if(down2[x]<1)or(down2[x]>n)then
                down2[x]:=0;
end;
begin
        readln(n);
        for i:=1 to n do
                read(h[i]);
        readln;
        for i:=0 to n+1 do
                z[i]:=i;
        kp(1,n);
        for i:=1 to n do
        begin
                l[z[i]]:=z[i-1];
                r[z[i]]:=z[i+1];
        end;
        for i:=1 to n do
                build(i);
        for i:=1 to n do
                if down2[i]>0 then
                begin
                        f[i,1,1]:=edge(i,down2[i]);
                        f[i,1,3]:=down2[i];
                        if down1[down2[i]]>0 then
                        begin
                                f[i,1,2]:=edge(down2[i],down1[down2[i]]);
                                f[i,1,3]:=down1[down2[i]];
                        end;
                end;
        for j:=2 to 20 do
                for i:=1 to n do
                        if(f[i,j-1,3]>0)and(f[f[i,j-1,3],j-1,3]>0)then
                        begin
                                f[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 do
        begin
                x:=jump(i,x0);
                if(a=0)and(b=0)then
                begin
                        j:=i;
                        a:=x[1];
                        b:=x[2];
                end
                else
                if(b=0)and(x[2]=0)and(h[i]>h[j])then
                begin
                        j:=i;
                        a:=x[1];
                        b:=x[2];
                end
                else
                if(x[2]<>0)and((b=0)or(x[1]/x[2]<a/b))then
                begin
                        j:=i;
                        a:=x[1];
                        b:=x[2];
                end;
        end;
        writeln(j);
        readln(m);
        for i:=1 to m do
        begin
                readln(a,b);
                x:=jump(a,b);
                writeln(x[1],' ',x[2]);
        end;
end.

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