@[fbexit](/user/361482) 你可以试试结构体
by liuzilin114514 @ 2024-02-18 19:31:46
@[fbexit](/user/361482) 也是这种思路
by liuzilin114514 @ 2024-02-18 19:33:16
确实是快排炸了。
在原数组上 shuffle 一下就行了。
by wangzikang @ 2024-02-18 19:37:25
@[fbexit](/user/361482) ```cpp
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<bits/stdc++.h>
using namespace std;
int bisai[1000010][2]={0};//记录了各个比赛的起始与终止时间
int main()
{
int n;
scanf("%d",&n);//有几个比赛
for(int i=0;i<n;i++)
{
scanf("%d %d",&bisai[i][0],&bisai[i][1]);//分别输入比赛的起始与终止时间
}
for(int i=1;i<=n;++i){
int x=rand()%n,y=rand()%n;
swap(bisai[x][0],bisai[y][0]);
swap(bisai[y][1],bisai[x][1]);
}
//为了尽可能参加比赛 应该选择结束时间最早的 那样才有足够的时间去参加下边的比赛
//所以应该按照结束时间从小到大排序
void quicksort(int bisai[][2],int low,int high);
quicksort(bisai,0,n-1);//排序已经完成
int cishu=0;//记录最大能参加几个比赛
int end=-1;
for(int i=0;i<n;i++)
{
if(bisai[i][0]>=end)//上一场结束要与下一场开始时间相同或者错开
{
cishu++;
end=bisai[i][1];
}
}
printf("%d\n",cishu);
return 0;
}
int position(int bisai[][2],int low,int high)//从小到大
{
int begin=bisai[low][0],end=bisai[low][1];
while(low<high)
{
while(low<high&&bisai[high][1]>=end)
high--;
bisai[low][0]=bisai[high][0];
bisai[low][1]=bisai[high][1];
while(low<high&&bisai[low][1]<=end)
low++;
bisai[high][0]=bisai[low][0];
bisai[high][1]=bisai[low][1];
}
bisai[low][0]=begin;
bisai[low][1]=end;
return low;
}
void quicksort(int bisai[][2],int low,int high)
{
if(low<high)
{
int axis=position(bisai,low,high);
quicksort(bisai,low,axis-1);
quicksort(bisai,axis+1,high);
}
}
```
by wangzikang @ 2024-02-18 19:38:29
```cpp
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<bits/stdc++.h>
using namespace std;
int bisai[1000010][2]={0};//记录了各个比赛的起始与终止时间
int main()
{
int n;
scanf("%d",&n);//有几个比赛
for(int i=0;i<n;i++)
{
scanf("%d %d",&bisai[i][0],&bisai[i][1]);//分别输入比赛的起始与终止时间
}
for(int i=1;i<=n;++i){
int x=rand()%n,y=rand()%n;
swap(bisai[x][0],bisai[y][0]);
swap(bisai[y][1],bisai[x][1]);
}
//为了尽可能参加比赛 应该选择结束时间最早的 那样才有足够的时间去参加下边的比赛
//所以应该按照结束时间从小到大排序
void quicksort(int bisai[][2],int low,int high);
quicksort(bisai,0,n-1);//排序已经完成
int cishu=0;//记录最大能参加几个比赛
int end=-1;
for(int i=0;i<n;i++)
{
if(bisai[i][0]>=end)//上一场结束要与下一场开始时间相同或者错开
{
cishu++;
end=bisai[i][1];
}
}
printf("%d\n",cishu);
return 0;
}
int position(int bisai[][2],int low,int high)//从小到大
{
int begin=bisai[low][0],end=bisai[low][1];
while(low<high)
{
while(low<high&&bisai[high][1]>=end)
high--;
bisai[low][0]=bisai[high][0];
bisai[low][1]=bisai[high][1];
while(low<high&&bisai[low][1]<=end)
low++;
bisai[high][0]=bisai[low][0];
bisai[high][1]=bisai[low][1];
}
bisai[low][0]=begin;
bisai[low][1]=end;
return low;
}
void quicksort(int bisai[][2],int low,int high)
{
if(low<high)
{
int axis=position(bisai,low,high);
quicksort(bisai,low,axis-1);
quicksort(bisai,axis+1,high);
}
}
```
by wangzikang @ 2024-02-18 19:39:08
@[liuzilin114514](/user/1191010) 也不行 可能就是排序的时候出问题了 但是一时半会找不到问题在哪
by fbexit @ 2024-02-18 19:40:37
@[wangzikang](/user/276621) 也是很感谢老哥的建议，也算是成功ac了
by fbexit @ 2024-02-19 15:29:51