网站没有备案怎么做支付,德阳房产网,iphone8多少钱,中职学校专业建设方案1. 一维差分
1.1. 小蓝的操作 1.1.1. 题目解析#xff1a;
这道题提到了对于“区间”进行操作#xff0c;而差分数列就是对于区间进行操作的好方法。
观察差分数列#xff1a;
给定数列#xff1a;1 3 5 2 7 1
差分数列#xff1a;1 2 2 -3 5 6
题目要求把原数组全部…1. 一维差分
1.1. 小蓝的操作 1.1.1. 题目解析
这道题提到了对于“区间”进行操作而差分数列就是对于区间进行操作的好方法。
观察差分数列
给定数列1 3 5 2 7 1
差分数列1 2 2 -3 5 6
题目要求把原数组全部变成1那就是说要让差分数组变成以1开头其余元素均为0的数列。题目又要求是最少操作次数对应于原数组来说就应该是每次都使得尽可能长的区间减1对于差分数列来说就是使i位置减1并且应该是不碰到负数的情况。 差分数列的第i个位置进行/-操作对于原数组来说就是从i往后的所有位置都进行同样的操作了。碰到负数了就不应该减1了因为最后的目标是使得所有后面的元素都是0也就意味着本次减1的操作区间到此中断了
所以就是让差分你数列的某个区间 一个1一个-1 对于一个区间进行操作让某个数字-1 从当前一直操作到末尾
最后要使得整个差分数列为10...0...0的形式操作的次数就是正数的次数归纳得到但是首位要为1所以还需要考虑的是将首位减到1就停止。
补充差分数列对于区间的操作 [l,r]操作a[l]d d[[r1]-d 给[l,r]的元素d[l,∞)操作a[l]d 给从l开始一直到末尾的元素都d
1.1.2. 代码
package lanqiao;import java.util.Scanner;/*** 一个数组 a 中共包含 n 个数问最少多少次操作可以让 a 数组所有数都变成 1。* 操作的内容是:每次操作可以任选一个区间使得区间内的所有数字减 1。数据保证一定有解。*/
public class 小蓝的操作 {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int[] a new int[n];for (int i 0; i n; i) {a[i]scanner.nextInt();}// 1. 得到差分数组int[] b new int[n];b[0] a[0];// 对于首位只减到1就停止if (b[0] 1) res b[0]-1;// 2. 本质上是对于差分数组进行修改for (int i 1; i n; i) {b[i] a[i] - a[i - 1];if (b[i] 0) resb[i];}System.out.println(res);}
}
