「蓝桥·算法双周赛」第二十七场蓝桥月赛最后一题题解

(可能是首发？？nm，真比第三题简单吧)

(求你们看看吧我对我的码风很自信)

问题描述

二分枚举时间m，然后剩下的就是根据题意纯模拟

注意备份和等待能不能跨天进行，这是个坑点

细节在注释里有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
package 蓝桥月赛第27场;

import java.util.Scanner;

public class F {
	
	private static int calculateDays(int m, int[] a, int[] b) {
		// 如果没有电脑需要备份，返回 0 天
    	if(a.length == 0) return 0;
    	
    	// 如果 M 小于第一台电脑的备份时间
    	if(m < a[0]) return Integer.MAX_VALUE;
    	
    	// 第一天
    	int days = 1;
    	// 备份第一台开始算剩余时间
    	int currentRemaining = m - a[0];
    	// 第一台都备份不上？？
        if (currentRemaining < 0) {
            return Integer.MAX_VALUE;
        }
        
        for (int i = 1; i <= a.length; i++) {
        	int wait = b[i];   // 获取前一台电脑的等待时间
        	
        	// 处理等待时间
        	// 时间足够，直接减去
        	if(currentRemaining >= wait) {
        		currentRemaining -= wait;
        	// 不够只能过天了，计算剩余的等待时间
        	}else {
        		// 把当天能等的给等了
        		wait -= currentRemaining;
        		days++;
        		currentRemaining = m;   // 重置剩余时间
        		
        		int fullDays = wait / m;   // 计算等几天
        		days += fullDays;
        		wait -= fullDays * m;
        		
        		if(wait > 0) {
        			// 减去零头
        			currentRemaining = m - wait;
        		}else {
        			currentRemaining = m;  // 重置
        		}
        	}
        	
        	
        	// 处理备份时间
        	// 今天够备份
        	if(currentRemaining >= a[i]) {
        		currentRemaining -= a[i];
        	}else {
        		// 今天备份不完，备份不能留到第二天
        		days++;
        		currentRemaining = m - a[i];
        		// 不行，时间太短，备份不完
        		if (currentRemaining < 0) {
        			return Integer.MAX_VALUE;
        		}
        	}
        	
        }
        return days;
    }
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		// N 台电脑
        int n = scanner.nextInt();
        // 最多允许的天数T
        int t = scanner.nextInt();
        // 表示每台电脑的备份时间。
        int[] a = new int[n];
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        
        // 每台电脑备份完成后需要等待的时间。
        int[] b = new int[n];
        for (int i = 1; i <= n; i++) {
            b[i] = scanner.nextInt();
        }
        scanner.close();
        
        // 最长备份时间
        int maxA = 0;
        for(int ai: a) {
        	if (ai > maxA) {
                maxA = ai;
            }
        }
        
        if (maxA > 3600) {
            System.out.println(-1);
            return;
        }
        
        // 开始二分 枚举m
        int left = maxA;
        int right = 3600;
        int result = -1;
        
        while(left <= right) {
        	int mid = (left + right) / 2;
        	int days = calculateDays(mid, a, b);
        	if (days <= t) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        System.out.println(result != -1 ? result : -1);
	}
}