盐城网站制作哪家好,响应式旅游网站模板,凤岗东莞微信网站建设,IT周末做网站违反制度么贪心问题
小A的糖果
题目描述
小 A 有 n n n 个糖果盒#xff0c;第 i i i 个盒中有 a i a_i ai 颗糖果。
小 A 每次可以从其中一盒糖果中吃掉一颗#xff0c;他想知道#xff0c;要让任意两个相邻的盒子中糖的个数之和都不大于 x x x#xff0c;至少得吃掉几颗糖…贪心问题
小A的糖果
题目描述
小 A 有 n n n 个糖果盒第 i i i 个盒中有 a i a_i ai 颗糖果。
小 A 每次可以从其中一盒糖果中吃掉一颗他想知道要让任意两个相邻的盒子中糖的个数之和都不大于 x x x至少得吃掉几颗糖。
输入格式
输入的第一行是两个用空格隔开的整数代表糖果盒的个数 n n n 和给定的参数 x x x。
第二行有 n n n 个用空格隔开的整数第 i i i 个整数代表第 i i i 盒糖的糖果个数 a i a_i ai。
输出格式
输出一行一个整数代表最少要吃掉的糖果的数量。
样例 #1
样例输入 #1
3 3
2 2 2样例输出 #1
1样例 #2
样例输入 #2
6 1
1 6 1 2 0 4样例输出 #2
11样例 #3
样例输入 #3
5 9
3 1 4 1 5样例输出 #3
0提示
样例输入输出 1 解释
吃掉第 2 盒中的一个糖果即可。 样例输入输出 2 解释
第 2 盒糖吃掉 6 6 6 颗第 4 盒吃掉 2 2 2 颗第 6 盒吃掉 3 3 3 颗。 数据规模与约定
对于 30 % 30\% 30% 的数据保证 n ≤ 20 n \leq 20 n≤20 a i , x ≤ 100 a_i, x \leq 100 ai,x≤100。对于 70 % 70\% 70% 的数据保证 n ≤ 1 0 3 n \leq 10^3 n≤103 a i , x ≤ 1 0 5 a_i, x \leq 10^5 ai,x≤105。对于 100 % 100\% 100% 的数据保证 2 ≤ n ≤ 1 0 5 2 \leq n \leq 10^5 2≤n≤105 0 ≤ a i , x ≤ 1 0 9 0 \leq a_i, x \leq 10^9 0≤ai,x≤109。
代码如下:
package exercise.luogu.greedy;import java.util.Scanner;public class P3817 {public static void main(String[] args) {long sum0;Scanner scannernew Scanner(System.in);int nscanner.nextInt();int xscanner.nextInt();int[] arrnew int[n];arr[0]scanner.nextInt();if(arr[0]x) {sumarr[0]-x;arr[0]x;}for(int i1;in;i) {arr[i]scanner.nextInt();if(arr[i]arr[i-1]x) {sumarr[i]arr[i-1]-x;arr[i]x-arr[i-1];}}System.out.println(sum);}
}总结
这道题特别水了,我当时没想起来,导致我最后也没独立写出来,这个就是俩俩一对,避免最后一个,所以把第一个当成特例!
分治问题
A-B 数对
题目背景
出题是一件痛苦的事情
相同的题目看多了也会有审美疲劳于是我舍弃了大家所熟悉的 AB Problem改用 A-B 了哈哈
题目描述
给出一串正整数数列以及一个正整数 C C C要求计算出所有满足 A − B C A - B C A−BC 的数对的个数不同位置的数字一样的数对算不同的数对。
输入格式
输入共两行。
第一行两个正整数 N , C N,C N,C。
第二行 N N N 个正整数作为要求处理的那串数。
输出格式
一行表示该串正整数中包含的满足 A − B C A - B C A−BC 的数对的个数。
样例 #1
样例输入 #1
4 1
1 1 2 3样例输出 #1
3提示
对于 75 % 75\% 75% 的数据 1 ≤ N ≤ 2000 1 \leq N \leq 2000 1≤N≤2000。
对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 2 × 1 0 5 1 \leq N \leq 2 \times 10^5 1≤N≤2×105 0 ≤ a i 2 30 0 \leq a_i 2^{30} 0≤ai230 1 ≤ C 2 30 1 \leq C 2^{30} 1≤C230。
2017/4/29 新添数据两组
代码如下:
package exercise.luogu.binary;import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class P1102 {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int c sc.nextInt();MapInteger, Integer map new HashMap();int []arrnew int[n];for (int i 0; i arr.length; i) {arr[i] sc.nextInt();map.put(arr[i], map.getOrDefault(arr[i],0)1);}long res0;for (int i 0; i arr.length; i) {int barr[i]-c;resmap.getOrDefault(b,0);}System.out.println(res);}
}
总结
这道题呢,反之就是说,要是知道map集合的这个方法的话会特别好写,我之前用过这个方法,但是这次我还是没有写出来,还是要多练多写多积累! map.put(arr[i], map.getOrDefault(arr[i],0)1);resmap.getOrDefault(b,0);
