题意:给定n长的序列，常数D

每次操作可以给某个数增加1.

问最少需要操作几次使得相邻的2个数的差值<=D

思路:

每次弹出队列里最大的数，然后更新就好了

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeSet;
import java.util.Queue;

public class Main {
	class Node implements Comparable
  
   {
		long num;
		int pos;
		Node(){}
		Node(long num, int pos)
		{
			this.num = num;
			this.pos = pos;
		}
		public int compareTo(Node o) {
			return Long.compare(o.num, num);
		}
		void put(){
			System.out.print(num+ +pos+ );
		}
		public Node clone(){
			Node he = new Node();
			he.num = this.num;
			he.pos = this.pos;
			return he;
		}
	}
	static int N = 100050;
	int n;
	long d, mx;
	long[] a = new long[N], b = new long[N];
	boolean[] vis = new boolean[N];
	PriorityQueue
   
     q = new PriorityQueue(); void dp(){ q.clear(); for(int i = 1; i <= n; i++) { vis[i] = true; q.add(new Node(a[i], i)); } while(q.size()>0){ Node u = q.poll(); vis[u.pos] = false; if(u.pos > 1 && b[u.pos-1]-u.num > d) u.num = b[u.pos-1]-d; if(u.pos < n && b[u.pos+1]-u.num > d) u.num = b[u.pos+1]-d; if(u.pos > 1 && u.num-b[u.pos-1] > d && vis[u.pos-1] == false){ vis[u.pos-1] = true; q.add(new Node(b[u.pos-1],u.pos-1)); } if(u.pos < n && u.num-b[u.pos+1] > d && vis[u.pos+1] == false){ vis[u.pos+1] = true; q.add(new Node(b[u.pos+1],u.pos+1)); } b[u.pos] = u.num; } } void init(){ n = cin.nextInt(); d = cin.nextLong(); mx = 0; for(int i = 1; i <= n; i++){ b[i] = a[i] = cin.nextLong(); mx = max(mx, a[i]); } } void work() { int T = cin.nextInt(); while(T-- > 0){ init(); dp(); long ans = 0; for(int i = 1; i <= n; i++)ans += b[i] - a[i]; out.println(ans); } } Main() { cin = new Scanner(System.in); out = new PrintWriter(System.out); } public static void main(String[] args) { Main e = new Main(); e.work(); out.close(); } public Scanner cin; public static PrintWriter out; int max(int x, int y) { return x > y  x : y; } int min(int x, int y) { return x < y  x : y; } double max(double x, double y) { return x > y  x : y; } double min(double x, double y) { return x < y  x : y; } long max(long x, long y) { return x > y  x : y; } long min(long x, long y) { return x < y  x : y; } static double eps = 1e-8; int abs(int x) { return x > 0  x : -x; } double abs(double x) { return x > 0  x : -x; } long abs(long x) { return x > 0  x : -x; } boolean zero(double x) { return abs(x) < eps; } }