蓝桥杯二分题

P1083 [NOIP2012 提高组] 借教室

题目描述

在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来 𝑛n 天的借教室信息，其中第 𝑖i 天学校有 𝑟𝑖ri​ 个教室可供租借。共有 𝑚m 份订单，每份订单用三个正整数描述，分别为 𝑑𝑗,𝑠𝑗,𝑡𝑗dj​,sj​,tj​，表示某租借者需要从第 𝑠𝑗sj​ 天到第 𝑡𝑗tj​ 天租借教室（包括第 𝑠𝑗sj​ 天和第 𝑡𝑗tj​ 天），每天需要租借 𝑑𝑗dj​ 个教室。

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 𝑑𝑗dj​ 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第 𝑠𝑗sj​ 天到第 𝑡𝑗tj​ 天中有至少一天剩余的教室数量不足 𝑑𝑗dj​ 个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

输入格式

第一行包含两个正整数 𝑛,𝑚n,m，表示天数和订单的数量。

第二行包含 𝑛n 个正整数，其中第 𝑖i 个数为 𝑟𝑖ri​，表示第 𝑖i 天可用于租借的教室数量。

接下来有 𝑚m 行，每行包含三个正整数 𝑑𝑗,𝑠𝑗,𝑡𝑗dj​,sj​,tj​，表示租借的数量，租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 11 开始的整数编号。

输出格式

如果所有订单均可满足，则输出只有一行，包含一个整数 00。否则（订单无法完全满足）

输出两行，第一行输出一个负整数 −1−1，第二行输出需要修改订单的申请人编号。

输入输出样例

输入 #1复制

4 3 
2 5 4 3 
2 1 3 
3 2 4 
4 2 4

输出 #1复制

-1 
2

说明/提示

【输入输出样例说明】

第 11份订单满足后，44天剩余的教室数分别为 0,3,2,30,3,2,3。第 22 份订单要求第 22天到第 44 天每天提供33个教室，而第 33 天剩余的教室数为22，因此无法满足。分配停止，通知第22 个申请人修改订单。

【数据范围】

对于10%的数据，有1≤𝑛,𝑚≤101≤n,m≤10；

对于30%的数据，有1≤𝑛,𝑚≤10001≤n,m≤1000；

对于 70%的数据，有1≤𝑛,𝑚≤1051≤n,m≤105；

对于 100%的数据，有1≤𝑛,𝑚≤106,0≤𝑟𝑖,𝑑𝑗≤109,1≤𝑠𝑗≤𝑡𝑗≤𝑛1≤n,m≤106,0≤ri​,dj​≤109,1≤sj​≤tj​≤n。

NOIP 2012 提高组 第二天 第二题

2022.2.20 新增一组 hack 数据

import java.io.*;// 主类，程序的入口
public class Main {// 用于从标准输入读取数据并进行词法分析的工具类实例，这里配置为从标准输入流读取private static final StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));// 用于向标准输出写入数据的实例private static final PrintWriter pw = new PrintWriter(System.out);// 表示天数private static int n;// 表示订单数量private static int m;// r[i]表示第i天可用于租借的教室数量private static int[] r;// d数组用于存储每份订单每天需要租借的教室数量private static int[] d;// s数组用于存储每份订单租借开始的天数private static int[] s;// t数组用于存储每份订单租借结束的天数private static int[] t;// diff[i]用于存储第i天与前一天可租借教室数量的差值（r[i] - r[i - 1]）private static int[] diff;// 从输入流中读取下一个整数的方法，通过StreamTokenizer解析并返回整数值private static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}// 读取输入数据的方法，包括天数、每天可租借教室数量以及各份订单信息private static void read() throws IOException {// 读取天数n = nextInt();// 读取订单数量m = nextInt();// 初始化r数组，长度为n + 1，索引从1开始对应天数r = new int[n + 1];// 初始化diff数组，长度为n + 1，用于记录相邻两天可租借教室数量差值diff = new int[n + 1];for (int i = 1; i <= n; ++i) {// 读取第i天可租借的教室数量r[i] = nextInt();// 计算第i天与前一天可租借教室数量的差值diff[i] = r[i] - r[i - 1];}// 初始化d数组，用于存储每份订单每天需要的教室数量d = new int[m];// 初始化s数组，用于存储每份订单租借开始天数s = new int[m];// 初始化t数组，用于存储每份订单租借结束天数t = new int[m];for (int i = 0; i < m; ++i) {// 读取每份订单每天需要租借的教室数量d[i] = nextInt();// 读取每份订单租借开始的天数s[i] = nextInt();// 读取每份订单租借结束的天数t[i] = nextInt();}}// 尝试根据给定的订单数量来判断是否能够满足这些订单的教室分配需求private static boolean solve(int index) {// book数组用于模拟教室数量的增减情况，类似一个差分数组的应用int[] book = new int[n + 1];// 根据前index份订单来更新book数组，模拟教室分配和回收情况for (int i = 0; i < index; ++i) {// 在租借开始的那天减去相应的教室需求数量，表示被占用了book[s[i]] -= d[i];// 如果租借结束的下一天还在天数范围内，则在那天加上相应的教室数量，表示归还了if (t[i] + 1 <= n) {book[t[i] + 1] += d[i];}}int num = 0;// 遍历每一天，计算累计的教室数量，看是否会出现负数（即教室不够用的情况）for (int i = 1; i <= n; ++i) {num += diff[i] + book[i];if (num < 0) {return false;}}return true;}// 程序的主入口方法public static void main(String[] args) throws IOException {// 先读取输入的天数、订单数量以及相关的教室和订单信息read();// 初始化二分查找的左右边界，left表示最小可能满足所有订单的情况（从第1份订单开始尝试）// right表示最大可能出现不满足情况（所有订单都尝试分配）int left = 1, right = m;int res = 0;// 二分查找过程，通过不断缩小范围来确定是哪份订单导致无法满足教室分配while (left <= right) {int mid = left + right >> 1;// 如果当前尝试的订单数量（mid份订单）能够满足教室分配需求if (solve(mid)) {// 说明可能更多的订单也能满足，将左边界右移，继续尝试更多订单left = mid + 1;} else {// 如果当前mid份订单无法满足教室分配需求，记录当前的mid值（可能就是导致不满足的订单编号）res = mid;// 缩小右边界，继续在左半边查找right = mid - 1;}}// 如果res不为0，说明存在订单无法满足，按照输出格式先输出-1if (res!= 0) {pw.println(-1);}// 输出需要修改订单的申请人编号（res的值就是那个编号，如果所有订单都能满足res就是0）pw.println(res);// 确保输出缓冲区的数据被刷新并输出到标准输出pw.flush();}
}

P4343 [SHOI2015] 自动刷题机

题目背景

曾经发明了信号增幅仪的发明家 SHTSC 又公开了他的新发明：自动刷题机——一种可以自动 AC 题目的神秘装置。

题目描述

自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。每秒，自动刷题机的代码生成模块会有两种可能的结果：

1.写了 𝑥x 行代码
2.心情不好，删掉了之前写的 𝑦y 行代码。（如果 𝑦y 大于当前代码长度则相当于全部删除。）

对于一个 OJ，存在某个固定的正整数长度 𝑛n，一旦自动刷题机在某秒结束时积累了大于等于 𝑛n 行的代码，它就会自动提交并 AC 此题，然后新建一个文件（即弃置之前的所有代码）并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机，得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的 𝑛n 究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了 𝑘k 道题，希望你计算 𝑛n 可能的最小值和最大值。

输入格式

第一行两个整数 𝑙,𝑘l,k，表示刷题机的日志一共有 𝑙l 行，一共了切了 𝑘k 题。

接下来 𝑙l 行，每行一个整数 𝑥𝑖xi​，依次表示每条日志。若 𝑥𝑖≥0xi​≥0，则表示写了 𝑥𝑖xi​ 行代码，若 𝑥𝑖<0xi​<0，则表示删除了 −𝑥𝑖−xi​ 行代码。

输出格式

输出一行两个整数，分别表示 𝑛n 可能的最小值和最大值。
如果这样的 𝑛n 不存在，请输出一行一个整数 −1−1。

输入输出样例

输入 #1复制

4 2
2
5
-3
9

输出 #1复制

3 7

说明/提示

数据规模与约定

• 对于 20%20% 的数据，保证 𝑙≤10l≤10；
• 对于 40%40% 的数据，保证 𝑙≤100l≤100 ；
• 对于 60%60% 的数据，保证𝑙≤2×103l≤2×103；
• 对于 100%100% 的数据，保证 1≤𝑙≤1051≤l≤105，−109≤𝑥𝑖≤109−109≤xi​≤109

import java.io.*;public class Main {// 用于从标准输入读取数据并进行词法分析的工具类实例，配置为从标准输入流读取private static final StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));// 用于向标准输出写入数据的实例private static final PrintWriter pw = new PrintWriter(System.out);// 表示刷题机的日志行数，即操作记录的数量private static int l;// 表示自动刷题机一共AC的题目数量private static int k;// x数组用于存储每条日志对应的操作（写代码行数或删代码行数）private static int[] x;// 从输入流中读取下一个整数的方法，通过StreamTokenizer解析并返回整数值private static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}// 读取输入数据的方法，包括日志行数、AC题目数量以及每条日志对应的操作信息private static void read() throws IOException {// 读取刷题机的日志行数l = nextInt();// 读取自动刷题机一共AC的题目数量k = nextInt();// 初始化x数组，长度为l，用于存储每条日志对应的操作信息x = new int[l];for (int i = 0; i < l; ++i) {// 依次读取每条日志对应的操作（写代码行数或删代码行数）x[i] = nextInt();}}// 根据给定的代码行数阈值n，模拟自动刷题机的工作过程，计算按照此阈值能AC的题目数量private static int solve(long n) {int cnt = 0; // 用于记录按照给定阈值能AC的题目数量long len = 0; // 用于记录当前积累的代码行数for (int i = 0; i < l; ++i) {// 累加当前操作对应的代码行数变化（写代码增加，删代码减少）len += x[i];// 如果当前积累的代码行数大于等于阈值n，或者代码行数小于0（可能删多了）if (len >= n || len < 0) {// 如果代码行数大于等于阈值，说明完成了一题，题目数量加1cnt += (len >= n? 1 : 0);// 无论哪种情况（完成一题或者代码删没了），都重新开始积累代码，将代码行数置0len = 0;}}return cnt;}// 通过二分查找的方式，在给定的区间内查找满足条件的代码行数阈值n// minFlag用于区分是查找最小值还是最大值，true表示查找最小值，false表示查找最大值private static long search(long left, long right, boolean minFlag) {long res = -1; // 用于记录最终查找到的满足条件的阈值，初始化为-1表示未找到while (left <= right) {long mid = left + right >> 1; // 取中间值作为当前尝试的阈值int cnt = solve(mid); // 根据当前中间阈值，计算能AC的题目数量if (cnt < k) {// 如果计算出的AC题目数量小于给定的k，说明阈值大了，缩小查找区间（右移右边界）right = mid - 1;} else if (cnt > k) {// 如果计算出的AC题目数量大于给定的k，说明阈值小了，扩大查找区间（左移左边界）left = mid + 1;} else {// 如果计算出的AC题目数量等于给定的k，说明找到了一个满足条件的阈值res = mid;if (minFlag) {// 如果是查找最小值，继续缩小查找区间，往更小的值方向找（右移右边界）right = mid - 1;} else {// 如果是查找最大值，继续扩大查找区间，往更大的值方向找（左移左边界）left = mid + 1;}}}return res;}// 程序的主入口方法public static void main(String[] args) throws IOException {// 先读取输入的日志行数、AC题目数量以及每条日志对应的操作信息read();// 如果日志行数小于AC题目数量，说明不可能存在满足条件的阈值，直接输出-1并结束程序if (l < k) {System.out.println(-1);return;}// 查找代码行数阈值n的最小值，传入初始查找区间和表示查找最小值的标识long min = search(1, (long) 10e14, true);// 如果未找到最小值（返回-1），说明不存在满足条件的阈值，输出-1并结束程序if (min == -1) {System.out.println(-1);return;}// 查找代码行数阈值n的最大值，传入初始查找区间和表示查找最大值的标识long max = search(1, (long) 10e14, false);// 输出找到的代码行数阈值n的最小值和最大值System.out.println(min + " " + max);}
}