首页 > 代码库 > hihoCoder 1051 补提交卡 最详细的解题报告
hihoCoder 1051 补提交卡 最详细的解题报告
题目来源:补提交卡
解题思路:假设未提交程序的天数为:a1,a2,....,an,补交的张数为M。依次从a1,a2,....,an中去掉连续的 K 天(0<=K<=M),然后再来计算剩余数组中最长连续提交天数。
具体算法(Java版,直接AC)
1 import java.util.Scanner; 2 3 public class Main { 4 5 //计算数组中最长连续提交天数 6 public static int getMax(int[] array) { 7 int[] copy = new int[array.length + 2]; 8 copy[0] = 0; 9 copy[array.length + 1] = 101;10 for (int i = 0; i < array.length; i++) {11 copy[i + 1] = array[i];12 }13 int max = Integer.MIN_VALUE;14 for (int i = 1; i < copy.length; i++) {15 int sum = copy[i] - copy[i - 1] - 1;16 max = max > sum ? max : sum;17 }18 return max;19 }20 21 //从下标为start开始,删除长度为count个元素22 public static int[] remove(int[] array, int count, int start) {23 int[] copy = new int[array.length - count];24 int index = 0;25 for (int i = 0; i < start; i++) {26 copy[index++] = array[i];27 }28 for (int i = start + count; i < array.length; i++) {29 copy[index++] = array[i];30 }31 return copy;32 }33 34 //计算使用k张补交卡后,最长连续提交天数35 public static int solve(int[] array, int k) {36 int max = Integer.MIN_VALUE;37 for (int i = 0; i <= array.length - k; i++) {38 int sum = getMax(remove(array, k, i));39 max = max > sum ? max : sum;40 }41 return max;42 }43 44 public static void main(String[] args) {45 Scanner scanner = new Scanner(System.in);46 int T = scanner.nextInt();47 while (T > 0) {48 int N = scanner.nextInt();49 int M = scanner.nextInt();50 int[] array = new int[N];51 for (int i = 0; i < N; i++) {52 array[i] = scanner.nextInt();53 }54 int max = Integer.MIN_VALUE;55 for (int i = 0; i <= M; i++) {56 int sum = solve(array, i);57 max = sum > max ? sum : max;58 }59 System.out.println(max);60 --T;61 }62 }63 }
hihoCoder 1051 补提交卡 最详细的解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。