我要招人

去企业版

首页 > 试题广场 >

小sun的假期

[编程题]小sun的假期

热度指数：2661 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小 sun 非常喜欢放假，尤其是那种连在一起的长假，在放假的时候小 sun 会感到快乐，快乐值等于连着放假的天数，现在小 sun 把他的安排表告诉你，希望你告诉他在他的安排表中，他的最大快乐值。

当某天没有安排的时候就是放假。

输入描述:

第一行两个数n,m，代表总共有n天，m个安排。

接下来有m行，每行是一个安排l,r，代表从第l天到第r天，小sun有安排了。

安排可能会重复。

输出描述:

输出一行，在这个安排表中，小sun最大的快乐值。

示例1

输入

5 1
2 3

输出

备注:

数据范围：

算法知识视频讲解

Silencer76

发表于 2025-11-27 10:06:22

对 pair 数组进行排序，先按再按。然后正序枚举一遍，比较当前的和前缀最大的。每次需要用 max 去维护前缀最大，而不是直接赋值，可能会出现这种情况。 n,m=map(int,input().split()) a=[tuple(map(int,input().split() 展开全文

godhands

发表于 2022-03-30 22:21:17

题目大意：找出n天中m个安排后1~n中没有安排的天数的最大连续值思路：类似于区间合并，不过不用合并这个步骤，只用上个区间的r 和下个区间的l维护ans就行代码实现： #include "iostream" #include "vector" #include "algorithm" usi 展开全文

jinii

发表于 2025-11-27 10:29:04

看到大家都写区间合并，我这里写一种经典的区间差分做法。对于一段区间[l,r]，把l赋值成1，r+1赋值成-1,扔到一个桶里，然后排序，从前往后遍历，并用一个sum记录值，当sum=0的时候就表示当前没有被覆盖，记录一下前一个的状态和位置，当前一个是0,就可以更新答案，最后关注一下尾部的情况。 #in 展开全文

ddb酱

发表于 2025-11-27 13:23:12

#include <bits/stdc++.h> using namespace std; #define endl "\n" #define all(a) a.begin(), a.end() using vpii = vector<pair<int, 展开全文

quchen666

发表于 2025-11-27 19:21:22

#include <bits/stdc++.h> using namespace std; const int N=1e5+10; typedef long long ll; struct Node { int l,r; }a[N]; bool cmp(Node a, 展开全文

花碗

发表于 2025-11-27 22:59:10

#include <iostream> #include<algorithm> using namespace std; const int N=100010; typedef pair<int,int> PII; PII p[N]; int main() { 展开全文

此在Dasein

发表于 2025-11-27 04:44:19

本题要求计算天安排中，最长的连续无安排（即放假）天数。由于总天数可能非常大（导致直接用数组标记会内存超限），但安排数量相对较小，因此我们采用事件点（扫描线）结合差分思想来解决此问题，将复杂度从依赖降到依赖。核心思想：关注变化点传统的差分数组需要长度为的数组来记录每一天的状态展开全文

牛客69596014号

发表于 2025-11-27 08:55:50

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(Sy 展开全文

自由的风0450

发表于 2025-11-27 09:59:04

n<1e9,采用区间合并 #include <iostream> #include<vector> #include<algorithm> using namespace std; int main() { ios::sync_with_stdio 展开全文

Masterr

发表于 2025-11-28 15:21:06

珂朵莉树模板题，根据输入维护区间，perform需要做的是统计连续没有被占用的区间长度 struct ODT { std::map<i32,i32> mp; ODT(i32 l, i32 r,i32 v=-1) { mp[l]=v; mp[ 展开全文

问题信息

难度：

6条回答 7收藏 69浏览

小sun的假期

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

相关试题