求助站外题

灌水区

Dream__Sky @ 2023-05-10 23:51:38

题目描述

小明跟他的小朋友们共n人商量在保证作业做完的前提下出去玩。第i个小朋友可以玩耍的时间是Si~Ti。这里Si~Ti表示的是时间段，比如Si=2,Ti=4，那么意味着这位小朋友在时刻1不能玩，时刻2、3、4可以去玩，时刻4以后都不能出去玩。如果在某个时刻，在一起玩的小朋友个数不少于k个，那么这一时刻就是幸福的。现在你要求出小朋友共有多少个时刻是幸福的。

输入

第一行：n k （n个小朋友，一起玩的小朋友达到k个为幸福）

第二行：S1 S2 … Sn

第三行：T1 T2 … Tn

输出

输出一行：幸福时刻数

样例输入输出

输入#1

4 3

1 2 2 4

5 2 4 6

输出#1

2

第2分钟和第4分钟一起玩耍的小朋友达到了3个所以是幸福的时刻，幸福时刻数2。

【数据规模】

对于50%的数据 n≤1000 1≤Si≤Ti≤1000

对于100%的数据 n≤100000 1≤Si≤Ti≤1000000000

求助满分思路，谢谢

by qifan_maker @ 2023-05-11 07:21:16

建议发学术区

by Fjionzy @ 2023-05-11 08:07:27

@Dream__Sky 哇，我们的比赛题也

by Fjionzy @ 2023-05-11 08:07:41

@Dream__Sky 你是南海区的？

by Fjionzy @ 2023-05-11 08:13:56

@Dream__Sky 

#include<bits/stdc++.h>
using namespace std;
int n,maxx,s,k,ans;
struct stu{
    int time,s;
}a[10000005];
bool cmp(stu a,stu b)
{
    if(a.time==b.time)
    return a.s>b.s;
    else
    return a.time<b.time;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        long long x;
        cin>>x;
        a[i].time=x;
        a[i].s++;
    }
    for(int i=1;i<=n;i++)
    {
        long long y;
        cin>>y;
        a[n+i].time=y+1;
        a[n+i].s--;
    }
    n*=2;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        s+=a[i].s;
        if(s>=k &&a[i].time!=a[i+1].time)
        {
            ans+=a[i+1].time-a[i].time;
        }
    }
    cout<<ans;
    return 0;
}

by Fjionzy @ 2023-05-11 08:14:30

@Dream__Sky 应该是这个，结构体二分

by eggegg185 @ 2023-05-11 09:47:03

@Dream__Sky 离散化然后暴力（（，记录一下两个被离散化的数原来的差是多少

by Dream__Sky @ 2023-05-11 16:22:34

@StarlitSky bushi

by Dream__Sky @ 2023-05-11 16:25:08

谢谢各位巨佬

by Fjionzy @ 2023-05-11 22:18:37

@Dream__Sky 话说对了没？

by Dream__Sky @ 2023-05-11 23:45:12

@StarlitSky 对了

|