免费WiFi

第一行包含两个数n(1 <= n <=1000), m (1 <= m <= 100)表示今天有n个人预约，以及路由单台最大连接个数m。
之后有n行，第i行有两个数字 [L, R] (1 <= L <= R <= 5000) 表示第i个人预约连接WiFi的时间是从L到R。

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 476K, 提交时间: 2023-04-21 16:42:23

#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int s[N];
int n,m;
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        s[l]++,s[r+1]--;
    }
    int maxi=0;
    for(int i=1;i<N;i++)s[i]+=s[i-1],maxi=max(maxi,s[i]);
    cout<<(maxi-1)/m+1;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 456K, 提交时间: 2021-09-07 21:42:53

#include<iostream> 
using namespace std;

int n,m,l,r,mx,flag[5003];

int main(){
	cin>>n>>m;
	while(n--){
		cin>>l>>r;
		for(int i=l;i<=r;i++){
			flag[i]++;
		}
	}
	for(int i=1;i<=5000;i++){
		if(flag[i]>mx)mx=flag[i];
	}
	cout<<(mx+m-1)/m<<endl;
	return 0;
}

Python3 解法, 执行用时: 63ms, 内存消耗: 4756K, 提交时间: 2023-05-29 09:45:04

n,m=map(int,input().split())
l=[0 for _ in range(5003)]
ans=0
for _ in range(n):
    a,b=map(int,input().split())
    l[a]+=1
    l[b+1]-=1
for i in range(5002):
    l[i]+=l[i-1]
print((max(l)+m-1)//m)

详情