前言
珂朵莉．诺塔．瑟尼欧里斯在一如往常的时间醒了过来，然后慢吞吞地走下床。
朝周围看了一圈才发现那里并不是她的房间，掌握到自己似乎是在医务室以后。
珂朵莉疑惑自己为什么会待在那样的地方，便回忆起昨晚最后发生过什么。
她想起来了。
珂朵莉的头"啵"地瞬间烧开了。
"什……什什什什什什……" 当时她脑筋烧坏了。
当时她心灵脆弱。
当时她失去了正常的判断力。
如果是在平时的精神状态下，她才不可能说出那种话，也不可能做出那种事。
讬词的借口要多少都想得到。然而就算搬出那些话，也无法颠覆已经发生过的事。
"万一我再过五天就会死，你能不能对我温柔一点？"
整体评价
t3, t4有点cf风格，t3是贪心+构造题，可以大胆猜测一下，t4的解法，用到"中位数定律"，对标第316周赛的t3。 推荐VP.
VP入口：第 42 场双周赛
更多解题报告详见：珂朵莉MM的解题报告汇总
T1. 无法吃午餐的学生数量
如果直接模拟的话, 大概是
不过这边不追求顺序，只求数量，因为只需要统计0/1的个数。
然后栈模拟， 大概是
class Solution {
public int countStudents(int[] students, int[] sandwiches) {
// 脑筋急转弯
int n0 = 0;
int n1 = 0;
for (int i = 0; i < students.length; i++) {
if (students[i] == 0) n0++;
else n1++;
}
// 暴力也行
for (int i = 0; i < sandwiches.length; i++) {
int v = sandwiches[i];
if (v == 0) {
if (n0 > 0) n0--;
else return n0 + n1;
} else {
if (n1 > 0) n1--;
else return n0 + n1;
}
}
return 0;
}
}T2. 平均等待时间
这类，两个变量的模拟题，一般是以时间变量为准线，然后进行模拟即可。
这边不需要额外的数据结构支持，应该题意限制只有一个Processor。
class Solution {
public double averageWaitingTime(int[][] customers) {
int n = customers.length;
long[] res = new long[n];
long acc = 0l;
long now = 0l;
for (int i = 0; i < n; i++) {
int[] q = customers[i];
now = Math.max(q[0], now);
now += q[1];
res[i] = (now - q[0]);
acc += res[i];
}
return acc * 1.0 / n;
}
}T3. 修改后的最大二进制字符串
贪心+构造题，感觉有点cf味了。
就是尽量把前面的0变成1，这边有个需要的特例是
[01...10] -> [001...1] -> [101...1]
可以理解为先退一步，从而达到进一步的效果, 而这个找[01..10]结构的过程，可以借助双指针优化。
因此整体的时间复杂度为.
class Solution {
// 贪心找规律吗？
// 找到连续的0111110, 就是这一个吗？
public String maximumBinaryString(String binary) {
char[] buf = binary.toCharArray();
int n = buf.length;
int j = 0;
for (int i = 0; i < n - 1; i++) {
if (buf[i] == '1') {
continue;
} else {
if (buf[i + 1] == '0') {
buf[i] = '1';
} else {
j = Math.max(i + 2, j);
while (j < n && buf[j] == '1') {
j++;
}
if (j < n && buf[j] == '0') {
buf[j] = '1';
buf[i + 1] = '0';
buf[i] = '1';
} else {
return new String(buf);
}
}
}
}
return new String(buf);
}
}比较考验思维， 中间也想过dp，循环节，甚至想打表找规律，但感觉不太靠谱, T_T.
T4. 得到连续 K 个 1 的最少相邻交换次数
这题的思维逻辑是，构建k个连续的1，所以本质就是选取一个包含k个1的区间，然后评估其代价即可。
可以用枚举法，就是枚举 这个k个1 的左端点。
现在给你一个区间，包含k个1， 那这个最小代价是多少呢？
最小化
这个问题，有没有特别像， 316周赛的t3，可以借助中位数猜想， 然后快速计算。
如果能快速评估的话，时间复杂度为, 那这题的总时间复杂度为
这边用滑窗的思想，这样评估代价，可以根据增量，快速计算出来。
class Solution {
// 枚举区间内的两个端点
// 那这题，就可以转换为 上周周赛t3，中位数的结论
public int minMoves(int[] nums, int k) {
List<Integer> arr = new ArrayList<>();
for (int i = 0;i < nums.length; i++) {
if (nums[i] == 1) {
arr.add(i);
}
}
long ans = 0;
// 中位数法则,
int s = 0, e = k - 1;
int m = (s + e) / 2;
for (int i = 0; i < k; i++) {
int delta = Math.abs(arr.get(i) - arr.get(m)) - Math.abs(m - i);
ans += delta;
}
int n = arr.size();
int ln = m - s, rn = e - m;
// *) 枚举法
long varval = ans;
for (int i = k; i < n; i++) {
s += 1;
m += 1;
e += 1;
// *) 处理完左侧
int t = arr.get(m) - arr.get(m - 1) - 1;
varval += (ln + 1) * t;
varval -= Math.abs(arr.get(s - 1) - arr.get(m)) - Math.abs(m - (s - 1));
// *) 处理右侧
varval -= rn * t;
varval += Math.abs(arr.get(e) - arr.get(m)) - Math.abs(m - e);
ans = Math.min(ans, varval);
}
return (int)ans;
}
}写在最后
