杨思越
2025 年6 月 8 日 02:48
1
3. 去宇宙比赛
题目ID：6005必做题100分
最新提交：
Wrong Answer
12 分
历史最高：
Wrong Answer
12 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
信友队要去宇宙参加比赛啦！一共有 N 个选手要乘坐一艘飞船，但是因为是在宇宙，所以对座位安排有点要求。飞船里面的位置安排有点像是飞机，有的座位与座位之间存在一些过道，将飞船分成了 M 个区间，每个区间 [l,r] 表示第 i 个区间的座位编号是从第 l 位到第 r 位，保证区间不重合，并且每一个座位只能坐一个人。为了让选手的乘坐体验，需要让选手之间的距离尽可能的远。现在想知道选手与选手之间的最小距离尽可能地大，请输出最大值。
输入格式
第一行包含一个正整数 T (1 ≤ T ≤ 1000)，代表有 T 艘飞船。对于每艘飞船，第一行包含两个正整数 N,M (1 ≤ N,M ≤ 10^5)，代表选手数和座位区间的数量。接下来 M 行，每行包含两个正整数 l,r (1 ≤ l,r ≤ 10^9)，代表这个区间的座位编号，保证区间不重合。注意：l 可能大于 r，如输入10 2，代表从第 10 个座位到第 2 个座位这个范围。所有测试数据的 N 之和 , M之和 均小于 10^6。
输出格式
对于每组数据输出一个正整数代表选手之间最小距离的最大值。特别的，若人数大于座位数，则输出 0 。若只有一人，那么输出这艘飞船的长度，即最右边座位的编号。
样例
Input 1
1 5 3 1 2 4 7 9 11
Output 1
2
样例解释
说明：对于第一个样例，选手与选手之间的最小距离可以通过让
数据范围
1 ≤ T ≤ 1000, 1 ≤ N,M ≤ 10^5, 1 ≤ l,r ≤ 10^9
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t;
int n,m;
struct box{
int l,r;
}a[100005];
bool cmp(box x,box y){
return x.l<y.l;
}
bool check(int x){
int seat=a[1].l;
int place=1;//这位选手坐在第几个区间里
for(int i=2;i<=n;i++){
int now=seat+x;
if(now<=a[place].r){
continue;
}
bool fl=1;
for(int j=place+1;j<=m;j++){
if(now<=a[j].l){
now=a[j].l;
place=j;
fl=0;
break;
}
}
if(fl){
return 0;
}
}
return 1;
}
int main(){
cin>>t;
while(t--){
cin>>n>>m;
ll cnt=0;//座位数
for(int i=1;i<=m;i++){
cin>>a[i].l>>a[i].r;
cnt+=(a[i].r-a[i].l+1);
}
if(cnt<n){
cout<<0<<endl;
continue;
}
sort(a+1,a+1+m,cmp);
if(n==1){
cout<<a[m].r<<endl;
continue;
}
int L=0;
int R=a[m].r/n;
while(L<=R){
int mid=(L+R+1)/2;
if(check(mid)){
L=mid+1;
}
else{
R=mid-1;
}
}
cout<<L-1<<endl;
}
return 0;
}
/*
*/我感觉这里是有问题的，你的now小于r之后，虽然放了人，但是一直没更新了
比如说(1,2) (10,11)，cnt算出来是4，但是我两个区间分别坐一个人，区间会比这个cnt大
1 个赞
杨思越
2025 年6 月 8 日 02:58
8
样例现在输出8了
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t;
int n,m;
struct box{
int l,r;
}a[100005];
bool cmp(box x,box y){
return x.l<y.l;
}
bool check(int x){
int seat=a[1].l;
int place=1;//这位选手坐在第几个区间里
for(int i=2;i<=n;i++){
int now=seat+x;
if(now<=a[place].r){
continue;
}
bool fl=1;
for(int j=place+1;j<=m;j++){
if(now<=a[j].l){
now=a[j].l;
place=j;
fl=0;
break;
}
}
if(fl){
return 0;
}
}
return 1;
}
int main(){
cin>>t;
while(t--){
cin>>n>>m;
ll cnt=0;//座位数
for(int i=1;i<=m;i++){
cin>>a[i].l>>a[i].r;
if(a[i].l>a[i].r){
swap(a[i].l,a[i].r);
}
cnt+=(a[i].r-a[i].l+1);
}
if(cnt<n){
cout<<0<<endl;
continue;
}
sort(a+1,a+1+m,cmp);
if(n==1){
cout<<a[m].r<<endl;
continue;
}
int L=0;
int R=1e9;
while(L<=R){
int mid=(L+R)/2;
if(check(mid)){
L=mid+1;
}
else{
R=mid-1;
}
}
cout<<R<<endl;
}
return 0;
}
/*
\__/
\ / \ /
—|o_o | —
/\ _ /\
/ \
00000000-0010-0824-0000-000000000000
0001
0000
0010
1000
0000
0100
*/
杨思越
2025 年6 月 8 日 03:01
11
这是个好问题,的确我忘更新seat(全局)了
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t;
int n,m;
struct box{
int l,r;
}a[100005];
bool cmp(box x,box y){
return x.l<y.l;
}
bool check(int x){
int seat=a[1].l;
int place=1;//这位选手坐在第几个区间里
for(int i=2;i<=n;i++){
int now=seat+x;
if(now<=a[place].r){
seat=now;
continue;
}
bool fl=1;
for(int j=place+1;j<=m;j++){
if(now<=a[j].l){
seat=a[j].l;
place=j;
fl=0;
break;
}
}
if(fl){
return 0;
}
}
return 1;
}
int main(){
cin>>t;
while(t--){
cin>>n>>m;
ll cnt=0;//座位数
for(int i=1;i<=m;i++){
cin>>a[i].l>>a[i].r;
if(a[i].l>a[i].r){
swap(a[i].l,a[i].r);
}
cnt+=(a[i].r-a[i].l+1);
}
if(cnt<n){
cout<<0<<endl;
continue;
}
sort(a+1,a+1+m,cmp);
if(n==1){
cout<<a[m].r<<endl;
continue;
}
int L=0;
int R=1e9;
while(L<=R){
int mid=(L+R)/2;
if(check(mid)){
L=mid+1;
}
else{
R=mid-1;
}
}
cout<<R<<endl;
}
return 0;
}
/*
*/
CZF2919
2025 年6 月 8 日 03:01
12
这里不是 continue 吧，应该是把他往后调到满足条件
杨思越
2025 年6 月 8 日 03:02
13
(不小心点了解决方案,赶紧撤了
这也有问题的，比如说我的now现在是5，遍历的时候有一个4-6的区间，你这个会直接忽略掉