CCF CSP认证 历年题目自练Day34

题目一

试题编号： 202303-1
试题名称： 田地丈量
时间限制： 1.0s
内存限制： 512.0MB
问题描述：
问题描述
西西艾弗岛上散落着 n 块田地。每块田地可视为平面直角坐标系下的一块矩形区域，由左下角坐标 (x1,y1) 和右上角坐标 (x2,y2) 唯一确定，且满足 x1

最近，顿顿想要在南山脚下开垦出一块面积为 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。

题目分析（个人理解）

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

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

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

4. 上代码!!!

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)

1
2
3
4
5
6
7
8
9
10

题目二

试题编号： 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

现在顿顿手中共有 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

全部的测试数据满足：0

题目分析（个人理解）

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

def judge(t,c,n,m,mid):
    zong=0
    for i in range(n):
        if t[i]>mid:
            zong+=(t[i]-mid)*c[i]
    if zong<=m:
        return True
    else:
        return False
 
 
n,m,k=map(int,input().split())
#待开垦的区域总数、顿顿手上的资源数量,每块区域的最少开垦天数
t=[]
c=[]
aa=0
for i in range(n):
    a,b=map(int,input().split())
    t.append(a)
    c.append(b)
    aa+=(a-k)*b
#print(t,c)
if aa<=m:
    print(k)
else:
    #二分
    l=k
    r=max(t)
    mid=0
    while(l<=r):
        mid=int((l+r)/2)
        if judge(t,c,n,m,mid):
            r=mid-1
        else:
            l=mid+1
    print(l)


 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

总结

忙而不乱，不骄不躁。
															--------shagzhaoyun 2023.10.17
1
2