1. 宝箱
题目描述
有一天，小 Q 发现了 n 个被上锁的宝箱和 m 串钥匙。第 i 个宝箱上写着一个整数 $a_j$，第 j 串钥匙上写着一个整数 $b_j$。小 Q 已经通过一些古籍得知了这些宝箱内有很多的珍贵的宝物，所以他想尽更多可能地打开这些宝箱。
当且仅当第 i 个宝箱上的数字 $a_j$ 与第 j 串钥匙上的数字 $b_j$ 之和为奇数的时候，这个宝箱才能被这串钥匙打开。每个宝箱只能被打开一次，且每串钥匙也只能被使用一次。
现在小 Q 想知道他最多能打开多少个宝箱，请你帮他计算出这个结果。
输出描述
第一行两个整数，n 和 m，表示宝箱的数量和钥匙串的数量
第二行 n 个整数，$a_1, a_2, …, a_n$，表示每个宝箱上的数字
第三行 m 个整数，$b_1, b_2, …, b_m$，表示每个钥匙上的数字
每两个数字之间用一个空格分隔
满足 $1 \le n, m \le 10^5$，$1 \le a_i \le 10^9$，$1 \le b_i \le 10^9$
输出描述
一个整数，表示最多能打开的宝箱的数量
示例1
输入：
2 2 1 1 1 1
输出：
0
解题说明
重点是宝箱和钥匙数字之和为奇数的时候才能打开，所以要么宝箱是奇数钥匙是偶数，要么宝箱是偶数钥匙是奇数。所以只要分别统计一下宝箱和钥匙的奇数和偶数的数量，就可以得到答案。即：
最多能打开的宝箱的数量 = min(偶数宝箱个数, 奇数钥匙个数) + min(奇数宝箱个数, 偶数钥匙个数)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int boxOdd = 0, boxEven = 0;
int keyOdd = 0, keyEven = 0;
for (int i = 0; i < n; i++) {
if (sc.nextInt() % 2 == 0) {
boxEven++;
} else {
boxOdd++;
}
}
for (int i = 0; i < m; i++) {
if (sc.nextInt() % 2 == 0) {
keyEven++;
} else {
keyOdd++;
}
}
System.out.println(Math.min(boxEven, keyOdd) + Math.min(boxOdd, keyEven));
}
}
2. 排队
题目描述
鹅厂的下午茶时间到！很多人都去了公司楼下的星巴克买咖啡。由于买咖啡的人很多，所以就排起了长长的队伍。
队伍当中有 n 个顾客，从 1 到 n 标号。一开始，每个顾客 i 在队伍当中的位置是 i。每个顾客有两个属性 $a_i$ 和 $b_i$。每个顾客的不满意度等于站在他前面的人与 $a_i$ 的乘积，加上站在他后面的人与 $b_i$ 的乘积。正式来说，假设顾客 i 位于位置 j，那么他的不满意度就等于 $a_i \times (j - 1) + b_i \times (n - j)$。
作为咖啡店的经理，本着顾客至上的原则，你需要重新安排每个顾客的位置，使得所有顾客的不满意度的总和最小。
输入描述
第一行一个整数 n，表示顾客的数量；
接下来 n 行，第 i 行包含两个整数 $a_i$ 和 $b_i$，用一个空格分隔；
满足 $1 \le n \le 10^5$，$1 \le a_i$，$bi \le 10^8$。
输出描述
一个整数，表示最小的不满意度的综合。
示例1
输入：
2 1 1 2 2
输出：
3
解题说明
题目来源：CodeForce: D. Stas and the Queue at the Buffet
如下所示，对不满意度的公式进行变换：
$$ a_i \times (j - 1) + b_i \times (n - j) = (a_i - b_i)j - a_i + nb_i $$
其中 $(- a_i + nb_i)$ 是常数项，满意度之和为：$S=\sum(a_i - b_i) \times j+C$。要让 S 最小，只需要对 $a_i - b_i$ 从大到小排序，让大的 $a_i - b_i$ 和小的 j 相乘即可。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n + 1];
int[] b = new int[n + 1];
Integer[] diff = new Integer[n + 1];
long res = 0;
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
b[i] = sc.nextInt();
diff[i] = a[i] - b[i];
res += n * (long) b[i] - a[i];
}
Arrays.sort(diff, 1, diff.length, (o1, o2) -> o2 - o1);
for (int i = 1; i <= n; i++) {
res += (long) diff[i] * i;
}
System.out.println(res);
}
}
3. 搬运工
题目描述
勤劳的搬运工在搬东西。
腾讯大厦一共有 m 名搬运工，公司有 n 个办公室排成一行，我们可以把这些办公室看做是数轴上坐标为 1 到 n 的每个位置，第 i 个办公室的箱子书为 $a_i$。
一开始搬运工们都在 0 点，每秒每名搬运工可以执行以下两种操作中的一个：
1、移动一个单位距离
2、搬走一箱东西（搬走之后该搬运工继续停留在该坐标处，可以继续往后走）
问你最少多少时间能搬走所有的东西呢？
输入描述
第一行两个数 n 和 m（$1 \le n$，$m \le 10^5$），含义见题意。
第二行 n 个数 $a_1, a_2, …, a_n$，$(0 \le a_i \le 10^9)$，分别表示每个办公室的箱子数量。
输出描述
一个数表示答案
示例1
输入：
4 100 3 4 5 4
输出：
5
解题说明
代码来自牛客网，主要思路就是二分法查找最小的 t，使得箱子能在时间 t 内搬完。所以实现了一个 check 函数，判断在规定时间内能否把箱子搬完。check 函数的原理我目前还弄不清楚。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] rooms = new int[n + 5];
long sum = 0;
int lastRoom = 0;
for (int i = 1; i <= n; i++) {
rooms[i] = sc.nextInt();
sum += rooms[i];
if (rooms[i] > 0) {
lastRoom = i;
}
}
long left = lastRoom + 1, right = sum + lastRoom;
while (left <= right) {
long mid = left + (right - left) / 2;
if (check(rooms, lastRoom, mid, m)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
System.out.println(left);
}
static boolean check(int[] rooms, int n, long time, int workers) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += rooms[i];
while (sum + i >= time) {
sum -= time - i;
if (--workers < 0) {
return false;
}
}
}
return workers != 0 || sum <= 0;
}
}
4. 期末总结
题目描述
小 Q 在每一个期末的时候，都会对本学期学习的情况做一次全面的总结，如果这个学期有 n 天，那么小 Q 会对每一天的学习状态打一个分，他对一段时间学习状态的评分为这段时间学习状态最低的分数与这段时间学习状态分数之和的乘积，小 Q 想知道他在这个学期中学习状态评分最高的时间段评分为多少呢？
输入描述
输入第一行将包含一个数字 n，代表本学期的天数，接下来的一行包含 n 个数字 $w_i(1 \le i \le n)$，代表每一天的学习状态分。$1 \le n$，$w_i \le 100000$
输出描述
输出一个数字，代表小 Q 在这个学期中学习状态评分最高的时间段评分。
示例1
输入：
5 7 2 4 6 5
输出：
60
解题说明
题目来源：POJ-2796
这是一道单调栈的题目，类似求柱状图中的最大矩形，差别是从（宽 * 区间中最小柱高）变成了（区间中柱高之和 * 区间中最小柱高）。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
static int[] array = new int[100005];
static long[] sum = new long[100005];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
array[i] = Integer.parseInt(st.nextToken());
sum[i] = sum[i - 1] + array[i];
}
array[++n] = -1;
long maxScore = 0;
Deque<Integer> stack = new LinkedList<Integer>();
stack.addFirst(0);
for (int i = 1; i <= n; i++) {
while (stack.size() > 1 && array[stack.getFirst()] > array[i]) {
long s = array[stack.removeFirst()] * (sum[i - 1] - sum[stack.getFirst()]);
if (s >= maxScore) {
maxScore = s;
}
}
stack.addFirst(i);
}
System.out.println(maxScore);
}
}
5. 花匠小Q
题目描述
花匠小 Q 养了两种花，一种红花一种白花，现在小 Q 用这些花进行摆放。摆放的时候连续的白花的数量只能是 k 的倍数（倍数可以为 0），不然就会枯萎。
现在给出 a 和 b，小 Q想知道长度为 [a, b] 的摆花方案中合法的摆花方案有多少种呢？
输入描述
第一行两个整数t，k。t 表示数据组数，k 见题意。
接下来 t 行每行两个整数，表示 $a_i, b_i$ $(1 \le a_i \le b_i \le 100000)$
输出描述
共 t 行，每行一个数，表示该 $[a_i, b_i]$ 下的摆花方案数。
示例1
输入：
3 2 1 3 2 3 4 4
输出：
6 5 5
说明：
对于区间 [1, 3]，合法方案有：红红红，白白红，红白白，红红，白白，红
对于区间 [2, 3]，合法方案有：红红红，拜拜红，红白白，红红，白白
对于区间 [4, 4]，合法方案有：红红红红，白白白白，白白红红，红红白白，红白白红
解题说明
从牛客网上学来的，如果 dp[n] 表示摆放 n 盆花的方案数，那么有两种可能：最后一盆是红花和最后一盆是白花。
- 最后一盆是红花的情况很简单，dp[n] = dp[n - 1]；
- 最后一盆是白花就比较麻烦，因为白花必须连续出现 k 的倍数次，
- 如果出现 k 次，那么 n - k 是红花，其后都是白花；
- 如果出现 2k 次，n - 2k 是红花，其后都是白花；
- …
- 依次类推。
所以，原来的状态定义不能满足需求，应该要定义两个状态：
dpR[n] 表示摆放 n 盆花，且最后一盆是红花的方案数；
dpW[n] 表示摆放 n 盆花，且最后一盆是白花的方案数。
这样的话，
dpR[n] = dpR[n - 1] + dpW[n - 1]
dpW[n] = dpR[n - k] + dpR[n - 2k] + dpR[n - 3k] + …
至于初始状态，无论 k 为何值，dpR[1] 肯定为 1，所以dpR[0] 和 dpW[0] 中有一个为 1，另一个为 0。
而 k = 1 时，dpW[1] = 1，而根据上面的递推公式，dpW[1] = dpR[0]，所以dpR[0] = 1，dpW[0] = 0。
import java.util.Scanner;
public class Main {
private static final int MOD = 1000000007;
private static final int N = 100000;
private static long[] sum = new long[N + 5];
private static void init(int k) {
// 最后一盆为红花
long[] dpR = new long[N + 5];
// 最后一盆为白花
long[] dpW = new long[N + 5];
dpR[0] = 1;
for (int i = 1; i <= N; i++) {
dpR[i] = (dpR[i - 1] + dpW[i - 1]) % MOD;
for (int j = k; j <= i; j += k) {
dpW[i] = (dpW[i] + dpR[i - j]) % MOD;
}
sum[i] = (sum[i - 1] + dpW[i] + dpR[i]) % MOD;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
int k = sc.nextInt();
init(k);
while ((t--) > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
System.out.println((sum[b] - sum[a - 1]) % MOD);
}
}
}