ACM实训冲刺第四天

本文主要是介绍ACM实训冲刺第四天，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【碎碎念】最近的任务有点繁重，所以考虑到实际情况，视频学习决定放置一段时间，重点是学校的实训练习题，对于我而言，目标不是优秀/良好，综合考虑我的实际情况，保佑我及格、顺利通过就可！加油！

---

今日学习任务

1.复习代码

2.习题（Cleaning Shifts、Vanya and Lanterns）

---

复习代码

Anton and Letters(搞定）

#include<stdio.h> 
int main(){int flag[26];for(int i=0;i<=26;i++) flag[i]=0;char tmp;while(tmp!='}'){scanf("%c",&tmp);if(tmp=='}') break;if(tmp<'z'&&tmp>='a'){flag[tmp-'a']++;//需要记忆 }}int cnt=0;//需要记得初始化 for(int i=0;i<26;i++){if(flag[i]>0) cnt++;}printf("%d",cnt);
}

Sum of Digits（搞定）

#include<stdio.h> 
#include<stdlib.h>
#include<string.h>char s[10000];
int sum=0;
int result =0;int main(){scanf("%s",s);while(1){if(strlen(s)==1) break;for(int i=0;i<strlen(s);i++){sum+=s[i]-'0';}itoa(sum,s,10);result++;}printf("%d",result);return 0;
}

寒冰王座（搞定）

#include<stdio.h> 
int main(){int T,i,n,sum;while(scanf("%d",&T)!=EOF){if(T<1||T>100) break;for(i=0;i<T;i++){scanf("%d",&n);if(n<1||n>10000) break;if(n>=300) sum=n%50;else if (n>=150&&n<200) sum=n-150;else if (n>=200&&n<300) sum=n-200;else if (n<150) sum=n;printf("%d\n",sum);}//if(n<1||n>10000) break;}return 0;
}

Charm Bracelet(搞定）

#include <stdio.h>
int main(){//第一行输入 两个空格分隔的整数int n,m;scanf("%d %d",&n,&m) ;//定义状态int dp[12881] ;//初始化dp[i]=0 for(int i=0;i<=m;i++){dp[i]=0;}//转移方程for(int i=1;i<=n;i++) {//注意  i=1 //定义重量和价值 两个空格分隔的整数描述魅力i： W i和D iint w,d;scanf("%d %d",&w,&d) ;for(int j=m;j>=w;j--){//注意j>=wif(dp[j-w]+d>dp[j])dp[j]=dp[j-w]+d;}}printf("%d\n",dp[m]);return 0;
}

习题

Cleaning Shifts

如果考试遇到这道题，可以先跳过

思路已掌握

问题

描述：

农夫大卫有一片菜园，同时他有n条狗（1 ≤ n ≤ 25000）来看守。他的每条狗有固定的工作时间，并且一定能在工作时间内好好看守菜园。他把一天的时间分为t个时间段(1 ≤ t ≤ 1000000)，分别是从1到t，希望每个时间段都至少有一条狗看守菜园。请你为这些狗分配工作，计算最少需要几条不同的狗，才能让每个时间段都至少有一条狗有看守菜园。注意，有可能不论怎么安排，都无法实现这个目标。

输入：

第一行输入是以空格分隔的两个整数n和t。第2行到第n+1行包含每条狗的工作时间，以两个空格分隔的整数表示，代表着这条狗工作的第一个时间段和最后一个时间段。

输出：

完成农夫大卫的目标需要的最少的狗的数量。如果不能完成该目标，输出-1。

样例1：

输入：
3 10
1 7
3 6
6 10输出：
2

样例2：

输入：
4 100
21 50
50 81
1 20
80 99输出：
-1

思路

【挑战程序设计竞赛 2章习题 poj 2376 Cleaning Shifts】 https://www.bilibili.com/video/BV13K421h7n5/?share_source=copy_web&vd_source=c1510692b9cb6018bf78570791d3ee02

代码思路

1. 定义结构体与输入：首先定义了一个结构体node来存储区间信息，包含起始时间a和结束时间b。通过scanf接收输入的区间数量n和总时间t，随后逐个读取每个区间的起始和结束时间。

2. 自定义排序：使用cmp函数作为比较器，实现了按区间起始时间升序排列，若起始时间相同则按结束时间降序排列，确保优先选择结束时间更晚的区间进行覆盖。通过sort函数对区间进行排序。

3. 区间覆盖判断与计数：

   • 首先检查第一个区间的起始时间是否为1，如果不是，则直接输出-1，表示无法覆盖整个区间。
   • 初始化end为第一个区间的结束时间，sum也为end，并设置已使用的区间计数cnt为1。
   • 遍历排序后的区间列表，对于每个区间，如果它的起始时间在当前已选区间结束时间的下一个位置或之内（即a[i].a<=end+1），则尝试更新最远的覆盖点为两者中的最大值（通过max(sum, a[i].b)）。
   • 如果当前区间的起始时间大于end+1，说明当前区间无法接续前一区间，此时需要判断是否可以形成新的覆盖段：如果新区间的起始时间仍然在当前覆盖段的结束时间之后（即a[i].a>end+1），则直接输出-1；否则，增加计数器cnt，并将end更新为上一覆盖段的最远端点，然后继续尝试将当前区间加入覆盖。
   • 最后，检查最终覆盖的最远端点end是否等于总时间t，如果不等则输出-1，表示未完全覆盖；否则输出cnt作为最少所需区间的数量。

记忆方法

1. 理解核心逻辑：关键是理解区间覆盖的贪心策略，即优先选择结束时间更晚的区间来尝试覆盖更长的连续时间线。

2. 掌握排序技巧：记住如何根据问题需求自定义排序规则，这里是为了在遍历时优先考虑起始时间早且结束时间晚的区间。

3. 区间迭代的分支处理：熟悉如何在遍历过程中分情况讨论区间能否连续覆盖，特别是如何通过更新end和sum变量来维护当前的覆盖状态。

4. 边界条件检查：特别注意代码中对边界条件的检查，比如起始时间不为1的情况，以及最终覆盖是否完整，这些是决定输出结果的关键。

代码

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <stdio.h>using namespace std;const int N = 1000010;/*
Sample Input3 10
1 7
3 6
6 10
Sample Output2
*/
int n;
struct Range
{int l, r;bool operator< (const Range& W)const{return l < W.l;}
}range[N];int main()
{int st, ed;scanf("%d%d", &n, &ed);st = 1;for (int i = 0; i < n; i++){int l, r;scanf("%d%d", &l, &r);range[i].l = l; range[i].r = r;}sort(range, range + n);int res = 0;bool success = false;for (int i = 0; i < n; i++){int j = i, r = -2e9;//所有区间起点在当前点前的  取终点最远的那个区间while (j < n && range[j].l <= st){r = max(r, range[j].r);j++;}//如果所有区间都在当前点之前  那就无法覆盖了 返回-1 跳出if (r < st){res = -1;break;}//选择区间个数加1res++;//选择后的所有区间已经覆盖到终点或者终点之后  那就得到了答案了if (r >= ed){success = true;break;}//更新当前点 继续下一轮寻找可覆盖的区间st = r + 1;i = j - 1;}if (!success) res = -1;printf("%d\n", res);return 0;
}

#include <iostream>
#include<algorithm>
#include <stdio.h>
using namespace std;
struct node
{int  a,b;
};
struct node a[2500005];
bool cmp(node a,node b)
{if(a.a==b.a) return a.b>b.b;else return a.a<b.a;
}
//结构体排序的比较函数
int main()
{int  t,n;scanf("%d%d",&n,&t);for(int i=1; i<=n; i++){scanf("%d%d",&a[i].a,&a[i].b);}
//习惯从1开始写sort(a+1,a+1+n,cmp);
//排序if(a[1].a!=1){printf("-1\n");return 0;}
//如果开头值都做不到等于1，那不管后面如何肯定覆盖不了所有区间int end=a[1].b,sum=end,cnt=1;
//因为先确定了end，所以cnt的值为1for(int i=2; i<=n; i++){if(a[i].a<=end+1){sum=max(sum,a[i].b);}
//若每次比较的左断点在上一段区间的里面或等于end+1即end的旁边，就不断进行比较满足条件中最远的点，即sum最大。else{end=sum;if(a[i].a>end+1){printf("-1\n");return 0;}else{cnt++;if(a[i].a<=end+1){sum=max(sum,a[i].b);}}}}if(end!=sum){cnt++;end=max(sum,end);}if(end!=t) printf("-1\n");else printf("%d\n",cnt);return 0;
}

Vanya and Lanterns

问题

一条长为 L 的路，在坐标轴上范围是 [0,L]，在 n个位置都放置了路灯，灯光能覆盖的半径相同，问半径至少为多少时灯光可以覆盖整条路。

Input

第一行包含两个整数 n,l(1≤n≤1000,1≤L≤109)分别代表路灯的数量和这条路的长度。
第二行包含 n个整数 ai(0≤ai≤L)，即各个路灯所在的位置。
注意：多个路灯可能在同一位置，而且可能有路灯位于这条路的端点。

Output

输出一个精确到小数点后 99 位的实数 r，代表能使灯光可以覆盖整条路的情况下，路灯灯光半径的最小值。

思路

解题说明：题目的意思是有一条长度为 l 的街道，在这条街道上放置了n个相同的灯，设从一端位置为0，每个灯的位置在ai处，问灯的最小照射半径为多少时，才能满足整条街道都能被灯光照到。此题可以用贪心来做，由于除了两端的两个灯之外，每两个灯之间都是由两个灯共同照射的，故只需要求出两两灯之间的距离一半的最大值，再求出两端两个灯距离街道两端尽头的距离，三者的最大值就是所求的最小半径。

代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;double ans=0;//半径 
int n;//路灯数量 
int l;//路的长度 
double loc[1001];//路灯所在位置 int main(){scanf("%d %d",&n,&l);for(int i=0;i<n;i++)//路灯的位置 scanf("%lf",&loc[i]);sort(loc,loc+n) ;for(int i=0;i<n;i++)//两两比较，求路灯最大值 ans=max(ans,(loc[i]-loc[i-1])/2.0) ;if(loc[0]!=0)//起始无路灯ans=max(ans,loc[0]) ;if(loc[n-1]!=l)//终点无路灯ans=max(ans,l-loc[n-1]) ;printf("%.010lf\n",ans);return 0;
}

这篇关于ACM实训冲刺第四天的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---