贝茜对她最近在农场周围造成的一切恶作剧感到抱歉,她同意帮助农夫约翰把一批新到的干草捆堆起来。 开始时,共有 N 个空干草堆,编号 1∼N。 约翰给贝茜下达了 K 个指令,每条指令的格式为 A B,这意味着贝茜要在 A..B 范围内的每个干草堆的顶部添加一个新的干草捆。 例如,如果贝茜收到指令 10 13,则她应在干草堆 10,11,12,13 中各添加一个干草捆。 在贝茜完成了所有指令后,约翰想知道 N 个干草堆的中值高度——也就是说,如果干草堆按照高度从小到大排列,位于中间的干草堆的高度。 方便起见,N 一定是奇数,所以中间堆是唯一的。 请帮助贝茜确定约翰问题的答案。 输入格式 第一行包含 N 和 K。 接下来 K 行,每行包含两个整数 A,B,用来描述一个指令。 输出格式 输出完成所有指令后,N 个干草堆的中值高度。 数据范围 1≤N≤106, 1≤K≤25000, 1≤A≤B≤N 输入样例: 7 4 5 5 2 4 4 6 3 5 输出样例: 1 样例解释 贝茜完成所有指令后,各堆高度为 0,1,2,3,3,1,0。 将各高度从小到大排序后,得到 0,0,1,1,2,3,3,位于中间的是 1。
时间: 2023-02-06 18:04:15 浏览: 51
算法1
(暴力枚举) $O(nk)$
时间复杂度
参考文献
python 代码
C++ 代码
java 代码
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
相关问题
贝茜对她最近在农场周围造成的一切恶作剧感到抱歉,她同意帮助农夫约翰把一批新到的干草捆堆起来。 开始时,共有 N 个空干草堆,编号 1∼N。 约翰给贝茜下达了 K 个指令,每条指令的格式为 A B,这意味着贝茜要在 A..B 范围内的每个干草堆的顶部添加一个新的干草捆。 例如,如果贝茜收到指令 10 13,则她应在干草堆 10,11,12,13 中各添加一个干草捆。 在贝茜完成了所有指令后,约翰想知道 N 个干草堆的中值高度——也就是说,如果干草堆按照高度从小到大排列,位于中间的干草堆的高度。 方便起见,N 一定是奇数,所以中间堆是唯一的。 请帮助贝茜确定约翰问题的答案。 输入格式 第一行包含 N 和 K。 接下来 K 行,每行包含两个整数 A,B,用来描述一个指令。 输出格式 输出完成所有指令后,N 个干草堆的中值高度。 数据范围 1≤N≤106, 1≤K≤25000, 1≤A≤B≤N 输入样例: 7 4 5 5 2 4 4 6 3 5 输出样例: 1 样例解释 贝茜完成所有指令后,各堆高度为 0,1,2,3,3,1,0。 将各高度从小到大排序后,得到 0,0,1,1,2,3,3,位于中间的是 1。
贝茜对她最近在农场周围造成的一切恶作剧感到抱歉,她同意帮助农夫约翰把一批新到的干草捆堆起来。
现在有 N 个空干草堆,编号为 1∼N。约翰给贝茜下达了 K 个指令,每条指令的格式为 A B,这意味着贝茜要在 A..B 范围内的每个干草堆的顶部添加一个新的干草捆。
例如,如果贝茜收到指令 10 13,则她应在干草堆 10,11,12,13 中各添加一个干草捆。
在贝茜完成了所有指令后,约翰想知道 N 个干草堆的中值高度——也就是说,如果干草堆按照高度从小到大排列,位于中间的干草堆的高度。
方便起见,N 一定是奇数,所以中间堆是唯一的。请帮助贝茜确定约翰问题的答案。
输入格式
第一行包含 N 和 K。
接下来 K 行,每行包含两个整数 A,B,用来描述一个指令。
输出格式
输出完成所有指令后,N 个干草堆的中值高度。
数据范围
1≤N≤106,
1≤K≤25000,
1≤A≤B≤N
输入样例:
7 4
5 5
2 4
4
贝茜是一头饥饿的牛。 每天晚上,如果牛棚中还有干草的话,贝茜都会吃掉其中的一捆。 初始时,牛棚中没有干草。 为了让贝茜不被饿死,农夫约翰制定了 N 个给贝茜送干草的计划。 其中第 i 个计划是在第 di 天的白天给贝茜送去 bi 捆干草。 这些计划互不冲突,保证 1≤d1<d2<…<dN≤T。 请你计算,贝茜在第 1∼T 天中有多少天有干草吃。 请用java做出来
以下是用Java编写的解决方案:
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt(); // 总天数
int N = scanner.nextInt(); // 计划数量
int[] days = new int[N]; // 计划执行的天数
int[] bundles = new int[N]; // 计划送去的干草捆数
for (int i = 0; i < N; i++) {
days[i] = scanner.nextInt();
bundles[i] = scanner.nextInt();
}
int[] hayAvailable = new int[T+1]; // 保存每天可用的干草捆数
for (int i = 0; i < N; i++) {
if (hayAvailable[days[i]] == 0) { // 如果这天还没有干草,则保存计划送去的干草捆数
hayAvailable[days[i]] = bundles[i];
} else { // 如果这天已经有干草,则累加计划送去的干草捆数
hayAvailable[days[i]] += bundles[i];
}
}
int count = 0; // 计数有干草的天数
for (int i = 1; i <= T; i++) {
if (hayAvailable[i] > 0) { // 如果这天有干草可供贝茜吃,则计数加一
count++;
}
}
System.out.println(count);
}
}
```
你可以使用上述代码来计算贝茜在第1~T天中有干草吃的天数。请注意,输入格式应符合以下要求:
- 第一行输入两个整数T和N,分别表示总天数和计划数量。
- 接下来的N行每行输入两个整数di和bi,分别表示给贝茜送去干草的天数和干草捆数。
希望这可以帮助到你!如有任何疑问,请随时提问。