蓝桥杯每日一题:挤牛奶(区间合并)

2024-04-08 22:28

本文主要是介绍蓝桥杯每日一题:挤牛奶(区间合并),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述:

每天早上 5 点,三名农夫去牛场给奶牛们挤奶。

现在从 5 点开始按秒计时,第一名农夫在第 300 秒开始给牛挤奶,并在第 1000 秒停止挤奶。

第二名农夫在第 700 秒开始给牛挤奶,并在第 1200 秒停止挤奶。

第三名农夫在第 1500 秒开始给牛挤奶,并在第 2100秒停止挤奶。

从开始挤奶到挤奶完全结束,这一期间,至少存在一名农夫正在挤奶的连续时间段的长度最长为 900秒(第 300 秒至第 1200 秒),完全没有任何农夫在挤奶的连续时间段的长度最长为 300 秒(第 1200秒至第 1500 秒)。

现在给你 N 名农夫挤 N 头奶牛的工作时间表,请你求出:

  1. 至少存在一名农夫正在挤奶的连续时间段的最长长度。
  2. 没有任何农夫在挤奶的连续时间段的最长长度。

注意:本题中给出的所有时间均为时刻(时间点),因此在本题中挤奶区间 [100,200]和 [201,300] 中间会有长度为 1 秒的间歇时间。

输入格式

第一行包含整数 N,表示农夫数量。

接下来 N 行,每行包含两个非负整数 l,r,表示农夫挤奶的开始时刻和结束时刻。

输出格式

共一行,包含两个整数,分别表示最长连续挤奶时间以及最长连续无人挤奶时间。

数据范围

1≤N≤5000,
0≤l≤r≤10^6,

输入样例:

3
300 1000
700 1200
1500 2100
输出样例:
900 300

解题思路:

读取所有挤奶的区间,将所有从小到大区间排序,遍历所有区间,如果有相交的地方就合并两区间,若不相交则要统计最长挤奶时间:当前区间r-l,最长不挤奶时间,要更新的区间的左端点-r,

更新区间l=i.x r=i.y;最有遍历完在更新一边最长挤奶时间。

参考代码:

#include <iostream>
#include <cstring>
#include <algorithm>#define x first
#define y secondusing namespace std;
typedef pair<int, int> PII;
const int N = 5010;
PII q[N];
int n;int main()
{cin>>n;for(int i=0;i<n;i++) cin>>q[i].x>>q[i].y;sort(q,q+n);int l = q[0].x,r = q[0].y;int m1 = 0,m2 = 0;for(int i=1;i<n;i++){if(r>=q[i].x) r = max(r,q[i].y);else{m1 = max(m1,r-l);m2 = max(m2,q[i].x - r);l = q[i].x,r = q[i].y;}}m1 = max(m1,r-l);printf("%d %d",m1,m2);return 0;
}

 

这篇关于蓝桥杯每日一题:挤牛奶(区间合并)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/886555

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

hdu4267区间统计

题意:给一些数,有两种操作,一种是在[a,b] 区间内,对(i - a)% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import

hdu4417区间统计

给你一个数列{An},然后有m次查询,每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead

hdu3333区间统计

题目大意:求一个区间内不重复数字的和,例如1 1 1 3,区间[1,4]的和为4。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

每日一练7:简写单词(含链接)

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1(错误经验) #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣(LeetCode) 2. LCR 098. 不同路径 - 力扣(LeetCode) 3. 63. 不同路径 II - 力扣(LeetCode) 1. 91. 解码方法 - 力扣(LeetCode) //思路:动态规划。 cl