小美拿到了一个数组,她每次可以进行如下操作:
选择两个元素,一个加 1,另一个减 1。
小美总共进行了次操作。她希望你回答最终数组是否是非降序,你能帮帮她吗?
请注意,元素可能会被减成负数!
第一行输入一个正整数 ,代表询问次数。
每次询问首先第一行输入两个正整数和,代表数组长度和操作次数。
接下来的一行输入个正整数 ,代表初始数组。
接下来的行,每行输入两个正整数,代表使得第个元素加 1,第个元素减 1。
输出行,每行输出该次询问的答案。
如果数组变成了非降序,则输出"Yes"。否则输出 "No"。
2 3 2 3 4 5 2 3 1 2 3 2 3 4 5 2 3 2 3
Yes No
第一组询问,操作两次后数组变成[4,4,4],为非降序。第二组询问,操作两次后数组变成[3,6,3],并不是非降序。
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); while (t-- != 0) { int n = in.nextInt(), k = in.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; ++i) a[i] = in.nextInt(); while (k-- != 0) { int u = in.nextInt(), v = in.nextInt(); a[u - 1]++; a[v - 1]--; } boolean f = true; for (int i = 1; i < n; ++i) { if (a[i] < a[i - 1]) { f = false; break; } } if (f) System.out.println("Yes"); else System.out.println("No"); } } }
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); while (in.hasNextInt()) { int n = in.nextInt(); int k = in.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; ++i) { arr[i] = in.nextInt(); } for (int j = 0; j < k; ++j) { int u = in.nextInt(); int v = in.nextInt(); arr[u - 1]++; arr[v - 1]--; } boolean sorted = true; for (int i = 1; i < n; ++i) { if (arr[i] < arr[i - 1]) { sorted = false; break; } } System.out.println(sorted ? "Yes" : "No"); } } }