牛客小白月赛17 A 小sun的假期

骑猪看日落 2023-10-11 09:37 13阅读 0赞

[传送门][Link 1]

题意：

第一行两个数n,m，代表总共有n天，m个安排。  
接下来有m行，每行是一个安排l,r，代表从第l天到第r天，小sun有安排了。  
安排可能会重复。

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

题解：

看到题目很明显就会想到取维护区间右端点或者区间左端点

![1633695-20190914130504839-393539442.png][]

maxx存放的是Li-l(这个是字符l，不是数字1)

比赛的时候排序函数里面忘加return导致错了。。。。。。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 #include<map>
     6 using namespace std;
     7 typedef long long ll;
     8 const int maxn=1e7+5;
     9 const int mod=26;
    10 struct shudui
    11 {
    12     ll l,r;
    13 }e[maxn];
    14 bool mmp(shudui x,shudui y)
    15 {
    16     if(x.l==y.l)
    17         return x.r<y.r;
    18     else return x.l<y.l;
    19 }
    20 int main()
    21 {
    22     ll n,m,maxx=0,sum=0;
    23     scanf("%lld%lld",&n,&m);
    24     for(ll i=1;i<=m;++i)
    25     {
    26         scanf("%lld%lld",&e[i].l,&e[i].r);
    27         sum=max(sum,e[i].r);
    28     }
    29     sort(e+1,e+1+m,mmp);
    30     //printf("%lld %lld\n",e[1].l,e[1].r);
    31     ll start=1,ends=0,flag=0;
    32     for(ll i=1;i<=m;++i)
    33     {
    34         if(ends>=e[i].l)
    35         {
    36             flag=1;
    37             ends=max(ends,e[i].r);
    38         }
    39         else
    40         {
    41             flag=0;
    42 
    43             start=ends+1;
    44             ends=e[i].r;//printf("%lld**%lld\n",start-1,ends);
    45         }
    46         if(!flag)
    47         {
    48             //last=e[i].l;
    49             //printf("%d %d %d\n",start,last,e[i].l);
    50             maxx=max(maxx,e[i].l-start);
    51             //printf("%lld %lld %lld\n",e[i].l,start,e[i].l-start);
    52         }
    53     }
    54     //printf("%lld\n",maxx);
    55     if(sum!=n)
    56     maxx=max(maxx,n-sum);
    57     printf("%lld\n",maxx);
    58     return 0;
    59 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11518903.html

[Link 1]: https://ac.nowcoder.com/acm/contest/1085/A
[1633695-20190914130504839-393539442.png]: https://img2018.cnblogs.com/blog/1633695/201909/1633695-20190914130504839-393539442.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif