在经过了整整10节课的学习之后，KDY的模拟赛还是一如既往的开始了。
第一次模拟赛，写篇补题报告吧。
一、比赛概况：
共3题，时间75分钟，每题100分（可能吧）
二、做题情况：
还算可以，打了120分，不算太高，但也还行（毕竟D4的难度吗。。。）
T1没分，T2 100/100，T3 20/100。
A：喷水装置(二) （喷水装置(一)是不是走丢了）（这是模拟赛里最难的一道题了，比赛的时候想了小40分钟，也没做出什么思路来，贪心+数学计算）
B：加油问题（几乎是2023 CSP-J复赛的T2，只有一点点差别，之前在D3也做过，所以不是很难）
C：数列极差问题（比较简单的贪心，但由于第一题时间费的有点多，没打完，骗了个样例）
今天的题就补一道T1，剩下两道把题目放在这，可以自己打打。
三、正文
1、加油问题
（1）题目：
时间限制：1秒 内存限制：128M
题目描述
你需要驾驶一辆卡车行驶 单位的距离。最开始时，卡车上有
单位的汽油。卡车每开
单位距离需要消耗
单位的汽油。
如果在途中车上的汽油耗尽，卡车就无法继续前进，因而无法到达终点。在途中一共有N个加油站。第 个加油站在距离起点
单位距离的地方，最多可以给卡车加
单位的汽油。假设卡车的燃料箱的容量是无限大的，无论加多少油都没有问题，那么请问卡车是否能到达终点、。如果可以，最少需要加多少次油？如果可以到达终点，输出最少的加油次数，否则输出-1。
限制条件：
输入描述
第一行用三个正整数描述，第一个正整数表示加油站个数，第二个正整数表示行驶距离，第三个正整数表示卡车原有多少汽油。
第二行输入每个加油站距离起点的距离。
第三行输入每个加油站可以给卡车加多少油。
输出描述
输出一行一个整数，表示最少需要加多少次油。
样例输入
4 25 10 10 14 20 21 10 5 2 4
样例输出
2
（2）AC代码：
什么？还想看AC代码？
自己打去。
2、数列极差问题
（1）题目：
时间限制：1秒 内存限制：128M
题目描述
在黑板上写了 个正整数组成的一个数列，进行如下操作： 每次擦去其中的两个数
和
，然后在数列中加入一个数
，如此下去直至黑板上 剩下一个数，在所有按这种操作方式最后得到的数中，最大的为
，最小的为
， 则该数列的极差定义为
。
请你编程，对于给定的数列，计算极差。
输入描述
输入包含多个测试集。每个测试集的第一个数N表示 正整数序列长度（ ），随后是
个正整数。
为
表示输入结束。
输出描述
每个结果一行。
样例输入
3 1 2 3 0
样例输出
2
（2）AC代码：
想得美，自己打去。
3、喷水装置(二)
正文开始！
（1）题目：
时间限制：1秒 内存限制：128M
题目描述
有一块草坪，横向长 ，纵向长为
，在它的橫向中心线上不同位置处装有
个点状的喷水装置，每个喷水装置
喷水的效果是让以它为中心半径为
的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。
输入描述
第一行输入一个正整数 ，表示共有
次测试数据。
每一组测试数据的第一行有三个整数，
，
，
表示共有
个喷水装置，
表示草坪的横向长度，
表示草坪的纵向长度。随后的
行，都有两个整数
和
，
表示第
个喷水装置的的横坐标（最左边为
），
表示该喷水装置能覆盖的圆的半径。
输出描述
每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。如果不存在一种能够把整个草坪湿润的方案，请输出 。
样例输入
2 2 8 6 1 1 4 5 2 10 6 4 5 6 5
样例输出
1 2
（2）逐步分析
看到这个题，我们肯定要先分析一下。看到这个题，题目中说了要用 个喷头来覆盖一整个草坪，所以我们就看一看，一个喷头是怎么覆盖一块地方的。举个例子：
如上图，蓝色区域即为喷头覆盖到的面积，绿色的区域就是草坪面积。
很明显，这个喷头显然不能用，因为它根本没什么用，连上面和下面的部分都覆盖不了。
所以，我们总结出来了一项规律： 小于半径的一半的喷头，我们
看！都！不！看！ 可以直接略过。
那么，对于一个能够覆盖到上下两部分（如下图）的喷头，我们该怎样存储和选择它呢？
我们看：对于一个圆心为 ，半径为
的喷头，它的真实覆盖面积是哪些呢？
是整个圆吗？很明显不是。
为什么呢？
我们知道，如果说我们就是按照这个题目描述的来去做，我们就会发现这是一个用圆覆盖长方形的问题，不太好解决。我们只能把它转化成一个长方形覆盖长方形的问题，进而就变成了一个区间覆盖问题。
所以，如果覆盖的面积是整个圆的话，那么A处的红色区域就会默认不喷了。但是红色区域实际并没有喷上水，那就和题意不符了。因此，我们需要从圆中找出一个最大的长方形，使得它的宽必须为 ，长度越长越好。看看图，它正好就是长方形
。
那么，我们就找出来了区间覆盖问题中的一些要素了。整理一下：
要覆盖的线段（区间）：。
每一个喷头，即每一个圆代表的小区间：。
有这些就够了。
那么，我们的大体的思路就是：
- 先输入，并且判断要不要直接舍去这个喷头；
- 然后根据题目中给出的每个喷头的坐标位置，计算出来它所代表的区间；
- 然后，套区间贪心中区间覆盖问题的模板即可。
接下来，又有了一个问题：怎么计算每个喷头代表的区间呢？
区间的长度怎么算呢？很简单。
其实就是让我们去算 的长度，一算出来，那就都解决了。
是一个直角三角形，那么运用勾股定理
，变形一下，
,那
就求出来了
那么，区间的坐标就很好确定了，就是
。
经过这一套转化后，我们还还剩一个区间覆盖问题就结束了。
区间覆盖问题比较基础，我就说一些关键词，不细说了，看到之后可以进行联想复习一下。（困，要睡觉）
区间覆盖：排序（ 从小到大，
从小到大，
从大到小，
从大到小）
包含关系的排除：还剩两种（ 从小到大，
从大到小）
选尽可能靠右的区间。进行优化：设一个变量 ，不考虑的地方
也
，下次从
开始遍历就可以了。
别忘了，千万不要在 循环之外输出答案！！（因为有多组样例）
那么，这道题就结束了。的确不很简单，但仔细思考一下还是能做出来的。
（3）AC代码：
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct zz
{
double l;
double r;
}a[10005];
int t,n,w,h;
bool cmp(zz a,zz b)
{
return a.l<b.l;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>w>>h;
double temp=h/2.0;
int xi,ri,cnt=0;
for(int i=1;i<=n;i++)
{
cin>>xi>>ri;
if(ri>temp)
{
double len=sqrt(ri*ri-temp*temp);
a[++cnt].l=xi-len;
a[cnt].r=xi+len;
}
}
sort(a+1,a+cnt+1,cmp); //转变成区域覆盖问题,按l从小到大排列
double pos=0,start=1; //遍历的起点
int ans=0;
while(pos<w)
{
double maxx=0;
for(int i=start;i<=cnt&&a[i].l<=pos;i++)
{
maxx=max(maxx,a[i].r);
start=i;
}
if(maxx==0) //上面没选到
{
cout<<n<<endl;
break;
}
ans++;
pos=maxx;
if(pos>=w)
{
cout<<ans<<endl;
break;
}
start++;
}
}
return 0;
}四、赛时自己的想法：
还可以。@yyz 一看第一题蛮难的，直接跳了，做了T2、T3拿了200分。第一题一开始的思路不对，做了小40分钟没做出来，当机立断换了T2。T2和T3其实挺简单的，正常来说应该能拿200分，但就是没时间了。。。还好打了120分，差点以为自己要爆零了。
原本以为后面的题应该会挺难的。。。
五、总结与反思：
先做简单的题，一个题时间超过20分钟还没写完就果断跳，不在这个题上钻牛角尖了。
贪心算法其实并不是很难，只要找到合适的贪心策略，把各种类型的问题的一般思路往上一套，就能基本上解决了。对于贪心的题目来说，最重要的就是看出它是一道贪心的题来，然后再想怎样把这道题的题目转化成一般的贪心问题，或者和一般的贪心问题联系起来。
下次就是令人闻风丧胆的DP模拟赛（还是公共子序列类的）了，我们下篇再见！！