手机做服务器搭网站,做app还是做网站合适,公司请做网站,深圳app定制开发外包公司P1083 [NOIP2012 提高组] 借教室 题目描述 在大学期间#xff0c;经常需要租借教室。大到院系举办活动#xff0c;小到学习小组自习讨论#xff0c;都需要向学校申请借教室。教室的大小功能不同#xff0c;借教室人的身份不同#xff0c;借教室的手续也不一样。 面对海量租… 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就是0pw.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 行代码若 0xi0则表示删除了 −−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);}
}
