题目链接 

C. Closest Cities

题目大意

• 一个数组，表示每个城市所在位置
• 每个城市之间距离定义为
• 一个城市到其他任意城市有代价为其距离大小的有向路
• 同时一个城市到离他最近的城市有代价为1的有向路
• 保证由小到大有序，且每个城市离他最近的只有一个
• 有次查询，问的最小代价

解题思路 

• 最短路？有多次查询，否
•  由于有序，可以将城市直接到达，看作依次经过之间的城市到达
• 这样走，代价只可能变小而不会变多（可能会经过代价为1的路）
• 同时，每个城市只用记录到其相邻城市的边，只有4条
• 建图？跑图？前缀和！
• 编号由小到大对正向边做一遍为，反过来再做一遍为
• 查询城市编号为
• 

import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;



public class Main{
	
	public static void main(String[] args) throws IOException{
		
		AReader input=new AReader();
	    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	    int T=input.nextInt();
	    while(true) {
	    	if(T==0) break;
	    	int n=input.nextInt();
	    	cnt=0;
	    	head=new int[n+1];
	    	e=new Edge[2*n+1];
	    	long[] a=new long[n+1];
	    	for(int i=1;i<=n;++i) {
	    		a[i]=input.nextLong();
	    	}
	    	long[] zheng=new long[n+1];
	    	long[] fan=new long[n+1];
//	    	addEdge(1, 2, 1);
	    	zheng[2]=1;//正向到i的花费
	    	fan[n-1]=1;
	    	for(int i=2;i<n;++i) {
	    		int l=i-1,r=i+1;
	    		
	    		if(a[i]-a[l]>a[r]-a[i]) {
	    			zheng[r]=zheng[i]+1;
//	    			addEdge(i, r, 1);
//	    			addEdge(i, l, a[i]-a[l]);
	    		}else {
	    			zheng[r]=zheng[i]+a[r]-a[i];
//	    			addEdge(i, l, 1);
//	    			addEdge(i, r, a[r]-a[i]);
	    		}
	    	}
//	    	addEdge(n, n-1, 1);
	    	for(int i=n-1;i>=2;--i) {
	    		int l=i-1,r=i+1;
	    		if(a[i]-a[l]>a[r]-a[i]) {
	    			fan[l]=fan[i]+a[i]-a[l];
	    		}else {
	    			fan[l]=fan[i]+1;
	    		}
	    	}
	    	int m=input.nextInt();
	    	while(true) {
	    		if(m==0)break;
	    		int s=input.nextInt();
	    		int t=input.nextInt();
	    		if(s<t) {
	    			out.println(zheng[t]-zheng▼显示);
	    		}
	    		else out.println(fan[t]-fan▼显示);
	    		
	    		m--;
	    	}
	    	T--;
	    }
		
		out.flush();
		out.close();
	}
	static
	class Node{
		int id;
		long dis;
		public Node(int I,long D) {
			id=I;
			dis=D;
		}
	}
	static int[] head;
	static int cnt;
	static Edge[] e;
	static 
	class Edge{
		int fr;
		int to;
		int nxt;
		long val;
	}
	static void addEdge(int fr,int to,long val) {
		cnt++;
		e[cnt]=new Edge();
		e[cnt].fr=fr;
		e[cnt].to=to;
		e[cnt].val=val;
		e[cnt].nxt=head[fr];
		head[fr]=cnt;
	}
	static
    class AReader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");
        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }
        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {
                String nextLine = innerNextLine();
                if (nextLine == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);
            }
            return true;
        }
        public String nextLine() {
            tokenizer = new StringTokenizer("");
            return innerNextLine();
        }
        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
 
        public long nextLong() {
            return Long.parseLong(next());
        }
 
    }
}

 D. Berserk Monsters

题目大意

• 有个点，每个点有
• 若左右与其相邻的点的，则该点删去，在下一轮不再出现
• 共进行轮，问每轮有多少个点被删去

解题思路 

• 若一个点在这一轮中没被删去，且它左右相邻的点没有变化，则在下一轮也不会被删
• 所以下一轮可能被删去的点，只会是这一轮被删去的点的左右相邻的点
• 很像的优化原理
• 用一个队列或是数组记录下一轮可能要删去的点进行探查，其余点不管
• 问题在于本轮删点和进行其左右端点的更新时同时的
• 而当更新右端点  的左端  时，可能右端点  也在本轮的探查队列中，但此时更新了其左端，计算出来的不是本轮的，而是下一轮的，会对判断是否在本轮删除产生影响
• 所以对于的更新，若在本轮队列中，则用缓存，当计算完当前轮的后，更新，否则直接更新，保持一致

import java.io.*;
import java.util.StringTokenizer;
import java.util.TreeSet;



public class Main{
	static
	class Node{
		int pre;
		int nxtpre;
		int nxt;
		boolean inqu1;
		boolean inqu2;
		boolean die;
		long a;
		long d;
	}
	public static void main(String[] args) throws IOException{
		
		AReader input=new AReader();
	    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	    
	    int T=input.nextInt();
	    while(true) {
	    	if(T==0) break;
	    	int n=input.nextInt();
		    Node[] mos=new Node[n+3];
		    for(int i=0;i<=n+1;++i) {
		    	mos[i]=new Node();
		    	mos[i].pre=i-1;
		    	mos[i].nxt=i+1;
		    	mos[i].nxtpre=i-1;
		    }
		    for(int i=1;i<=n;++i)mos[i].a=input.nextLong();
		    for(int i=1;i<=n;++i)mos[i].d=input.nextLong();
		    int ans=0;
		    int[] qu1=new int[n+1];
		    int[] qu2=new int[n+1];
		    int cnt1=0;
		    int cnt2=0;
		    
		    for(int i=1;i<=n;++i) {
		    	int pre=mos[i].pre;//旧的
		    	int nxt=mos[i].nxt;
		    	long A=mos[pre].a+mos[nxt].a;
		    	mos[i].pre=mos[i].nxtpre;//下一轮的
		    	pre=mos[i].pre;
		    	if(A>mos[i].d) {
		    		ans++;
		    		mos[i].die=true;
		    		if(!mos[pre].inqu1&&pre!=0) {
		    			mos[pre].inqu1=true;
		    			cnt1++;
		    			qu1[cnt1]=pre;
		    		}
		    		if(!mos[nxt].inqu2&&nxt!=n+1) {
		    			mos[nxt].inqu1=true;
		    			cnt1++;
		    			qu1[cnt1]=nxt;
		    		}
		    		mos[pre].nxt=mos[i].nxt;
		    		mos[nxt].nxtpre=mos[i].pre;//初始肯定都在
		    	}
		    }
		    out.print(ans+" ");
		    for(int t=2;t<=n;++t) {
		    	if(t%2==0) {
		    		ans=0;
		    		for(int o=1;o<=cnt1;++o) {
		    			int i=qu1[o];
		    			mos[i].inqu1=false;
		    			if(mos[i].die)continue;
		    			int pre=mos[i].pre;//旧的
		    	    	int nxt=mos[i].nxt;
		    	    	long A=mos[pre].a+mos[nxt].a;
		    	    	mos[i].pre=mos[i].nxtpre;//下一轮的
		    	    	pre=mos[i].pre;
		    	    	if(A>mos[i].d) {
		    	    		ans++;
		    	    		mos[i].die=true;
		    	    		if(!mos[pre].inqu2&&pre!=0) {
		    	    			mos[pre].inqu2=true;
		    	    			cnt2++;
		    	    			qu2[cnt2]=pre;
		    	    		}
		    	    		if(!mos[nxt].inqu2&&nxt!=n+1) {
		    	    			mos[nxt].inqu2=true;
		    	    			cnt2++;
		    	    			qu2[cnt2]=nxt;
		    	    		}
		    	    		mos[pre].nxt=mos[i].nxt;
		    	    		if(mos[nxt].inqu1)mos[nxt].nxtpre=mos[i].pre;
		    	    		else {
		    	    			mos[nxt].pre=mos[i].pre;
		    	    			mos[nxt].nxtpre=mos[i].pre;
		    	    		}
		    	    	}
		    		}cnt1=0;
		    		out.print(ans+" ");
		    	}else {
		    		ans=0;
		    		for(int o=1;o<=cnt2;++o) {
		    			int i=qu2[o];
		    			mos[i].inqu2=false;
		    			if(mos[i].die)continue;
		    			int pre=mos[i].pre;//旧的
		    	    	int nxt=mos[i].nxt;
		    	    	long A=mos[pre].a+mos[nxt].a;
		    	    	mos[i].pre=mos[i].nxtpre;//下一轮的
		    	    	pre=mos[i].pre;
		    	    	if(A>mos[i].d) {
		    	    		ans++;
		    	    		mos[i].die=true;
		    	    		if(!mos[pre].inqu1&&pre!=0) {
		    	    			mos[pre].inqu1=true;
		    	    			cnt1++;
		    	    			qu1[cnt1]=pre;
		    	    		}
		    	    		if(!mos[nxt].inqu1&&nxt!=n+1) {
		    	    			mos[nxt].inqu1=true;
		    	    			cnt1++;
		    	    			qu1[cnt1]=nxt;
		    	    		}
		    	    		mos[pre].nxt=mos[i].nxt;
		    	    		if(mos[nxt].inqu2)mos[nxt].nxtpre=mos[i].pre;
		    	    		else {
		    	    			mos[nxt].pre=mos[i].pre;
		    	    			mos[nxt].nxtpre=mos[i].pre;
		    	    		}
		    	    	}
		    		}cnt2=0;
		    		out.print(ans+" ");
		    	}
		    }
		    T--;
		    out.println();
	    }
	    out.flush();
	    out.close();
	}
	
	static
    class AReader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");
        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }
        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {
                String nextLine = innerNextLine();
                if (nextLine == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);
            }
            return true;
        }
        public String nextLine() {
            tokenizer = new StringTokenizer("");
            return innerNextLine();
        }
        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
 
        public long nextLong() {
            return Long.parseLong(next());
        }
 
    }
}