首页 > 代码库 > 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 补提交卡 最详细的解题报告