CCFCSP认证历年题目自练Day34

题目一

试题编号： 202303-1 试题名称： 田地丈量 时间限制： 1.0s 内存限制： 512.0MB 问题描述： 问题描述 西西艾弗岛上散落着 n 块田地。每块田地可视为平面直角坐标系下的一块矩形区域，由左下角坐标 (x1,y1) 和右上角坐标 (x2,y2) 唯一确定，且满足 x1<x2、y1<y2。这 n 块田地中，任意两块的交集面积均为 0，仅边界处可能有所重叠。

最近，顿顿想要在南山脚下开垦出一块面积为 a×b 矩形田地，其左下角坐标为 (0,0)、右上角坐标为 (a,b)。试计算顿顿选定区域内已经存在的田地面积。

输入格式 从标准输入读入数据。

输入共 n+1 行。

输入的第一行包含空格分隔的三个正整数 n、a 和 b，分别表示西西艾弗岛上田地块数和顿顿选定区域的右上角坐标。

接下来 n 行，每行包含空格分隔的四个整数 x1、y1、x2 和 y2，表示一块田地的位置。

输出格式 输出到标准输出。

输出一个整数，表示顿顿选定区域内的田地面积。

样例输入 4 10 10 0 0 5 5 5 -2 15 3 8 8 15 15 -2 10 3 15 Data

样例输出 44 Data

样例解释 如图所示，选定区域内田地（绿色区域）面积为 44。 子任务 全部的测试数据满足 n≤100，且所有输入坐标的绝对值均不超过 104。

题目分析（个人理解）

还是先看输入，第一行输入n个田地，a，b是想要开垦的田地的右上角坐标(x2,y2)，左下角坐标是（x1=0,x2=0）后面的n行输入每一块已经开垦好的田地的左下角坐标和右上角坐标，现在要求重复的面积。

我选择二维列表l[]存储每块田地的坐标，如何判断重叠部分是整个问题的核心，对于超过边界的情况有如下几种情况：黄色是要开垦的土地，蓝色是已经开垦过的土地。

我们可以这样理解求重叠部分面积就是重叠部分的长乘宽，如何确定？不难发现，长就是x2与a取最小值减去x1与0取最大值。宽就是y2与b取最小值减去x2与0取最大值。在判断如果长和宽都大于0相乘即可，然后遍历所有蓝色矩形再相加就完事了。

上代码!!!

n, a, b = map(int, input().split()) l = [[i for i in map(int, input().split())] for j in range(n)]#列表推导式创建二维列表 sum = 0#计算总重合面积 for i in range(n): x = min(a, l[i][2])-max(0, l[i][0]) y = min(b, l[i][3])-max(0, l[i][1]) if x>=0 and y>=0: sum += x*y print(sum) 题目二

试题编号： 202303-2 试题名称： 垦田计划 时间限制： 1.0s 内存限制： 512.0MB 问题描述： 问题描述 顿顿总共选中了 n 块区域准备开垦田地，由于各块区域大小不一，开垦所需时间也不尽相同。据估算，其中第 i 块（1≤i≤n）区域的开垦耗时为 ti 天。这 n 块区域可以同时开垦，所以总耗时 tTotal 取决于耗时最长的区域，即：tTotal=max{t1,t2,⋯,tn}

为了加快开垦进度，顿顿准备在部分区域投入额外资源来缩短开垦时间。具体来说：

在第 i 块区域每投入 ci 单位资源，便可将其开垦耗时缩短 1 天；

耗时缩短天数以整数记，即第 i 块区域投入资源数量必须是 ci 的整数倍；

在第 i 块区域最多可投入 ci×(ti−k) 单位资源，将其开垦耗时缩短为 k 天；

这里的 k 表示开垦一块区域的最少天数，满足 0<k≤min{t1,t2,⋯,tn}；换言之，如果无限制地投入资源，所有区域都可以用 k 天完成开垦。

现在顿顿手中共有 m 单位资源可供使用，试计算开垦 n 块区域最少需要多少天？

输入格式 从标准输入读入数据。

输入共 n+1 行。

输入的第一行包含空格分隔的三个正整数 n、m 和 k，分别表示待开垦的区域总数、顿顿手上的资源数量和每块区域的最少开垦天数。

接下来 n 行，每行包含空格分隔的两个正整数 ti 和 ci，分别表示第 i 块区域开垦耗时和将耗时缩短 1 天所需资源数量。

输出格式 输出到标准输出。

输出一个整数，表示开垦 n 块区域的最少耗时。

样例输入1 4 9 2 6 1 5 1 6 2 7 1

样例输出1 5

样例解释 如下表所示，投入 5 单位资源即可将总耗时缩短至 5 天。此时顿顿手中还剩余 4 单位资源，但无论如何安排，也无法使总耗时进一步缩短。

i 基础耗时 ti 缩减 1 天所需资源 ci 投入资源数量 实际耗时 1 6 1 1 5 2 5 1 0 5 3 6 2 2 5 4 7 1 2 5 样例输入2 4 30 2 6 1 5 1 6 2 7 1

样例输出2 2

样例解释 投入 20 单位资源，恰好可将所有区域开垦耗时均缩短为 k=2 天；受限于 k，剩余的 10 单位资源无法使耗时进一步缩短。

子任务 70% 的测试数据满足：0<n,ti,ci≤100 且 0<m≤106；

全部的测试数据满足：0<n,ti,ci≤105 且 0<m≤109。

题目分析（个人理解） 题目还是比较好理解的，两种样例分别给出了不同的用资源之后的情况。还是常规，先看输入，第一行输入n个田地，m个资源，k表示开垦一块地的最小天数。后面的n行输入每一块田地的耗时（不使用资源的情况下需要的天数）和使用资源的最小单位，使用一个最小单位只能减少一天。我选择列表存储， t = []#在不投入资源的情况下的耗时 t.append(0) c = []#资源的最小单位 c.append(0) 列表的位序表示第几块地（也就是从1开始）每一行追加写入即可（.append()方法）。之后到核心部分，如何找到在资源用完的情况下开垦完所有的田地的天数。我是这样想的，在第day天能完成所有田地的开垦，那么需要消耗多少资源？如果消耗的资源大于拥有的资源m那么就查找第day+1需要的资源（资源不够又要完成所有土地的开垦，只能牺牲时间）。如果在第day天需要的资源小于拥有的资源m那么就用资源换时间，去找day-1天需要的资源。如何计算第day天完成需要的资源？自定义函数用来计算需要的资源，如果当前天数day(函数的参数)大于t[i]说明不用资源都开垦完了,反之当前天数day小于t[i]说明需要用资源来填补。用计数器totalM统计需要多少资源，那么totalM += (t[i] - day) * c[i]#资源的使用的最小单位是c[i]，需要补t[i]-day天。OK，现在将在第day天完成需要的资源全部知道了，下面采用二分查找算法（数据结构内容），找到满足题目条件的天数。二分查找算法： 原理：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。对于这道题，先找到最小天数，也就是k，最大天数为t[]中的最大值，先计算天数为(L+R)/2时，需要消耗的资源totalM；如果消耗资源超过拥有资源，只能增加天数，减少资源消耗。反之如果消耗资源未超过拥有资源，消耗资源少了，还可以减少天数，消耗更多的资源。上代码！！！ ###### 数据读入 ###### n, m, k = map(int, input().split()) t = []#在不投入资源的情况下的耗时 t.append(0) c = []#资源的最小单位 c.append(0) for i in range(1,n+1): tmpT, tmpC = map(int, input().split()) t.append(tmpT) c.append(tmpC) ###### 计算天数对应的资源消耗 ###### def countTotalM(day):#参数day是想在第几天完成 totalM = 0 for i in range(1, n+1): if day >= t[i]:#如果当前天数大于t[i]说明不用资源都开垦完了 continue else: #当前天数小于t[i]说明需要用资源来填补 totalM += (t[i] - day) * c[i]#资源的使用的最小单位是c[i]，需要补t[i]-day天 return totalM ###### 二分法 ###### R = max(t) L = k while(L<=R): # 计算天数为(L+R)/2时，需要消耗的资源totalM mid = int((L + R) / 2) totalM = countTotalM(mid) if totalM > m: # 消耗资源超过拥有资源，只能增加天数，减少资源消耗 L = mid + 1 else: # 消耗资源少了，还可以减少天数，消耗更多的资源 R = mid - 1 print(L) 总结 忙而不乱，不骄不躁。 --------shagzhaoyun 2023.10.17