社区讨论
求判断代码是否正确
学术版参与者 3已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mhizxni9
- 此快照首次捕获于
- 2025/11/03 18:27 4 个月前
- 此快照最后确认于
- 2025/11/03 18:27 4 个月前
这是自己写的代码,题目也是自己给的,而题目大概是这样的
给出 个区间的起点与终点,并且给出 个点的位置,要求从 个点中选最少数量的点以达到每个区间至少覆盖了一个点的目标
输入格式
第一行:两个正整数, 与
接下来 行:每行两个非负数,其中第 行表示第 个区间的起点与终点
接下来一行: 个非负数,其中第 个表示第 个点的坐标
输出格式
一行,表示至少选几个点
时空限制
满足 且
我的代码
CPP#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+5;
struct node
{
int st;
int end;
}a[N];
int n;
int m;
int cnt;
int pos[N];
int last_pos;
bool cmp(node x,node y)
{
return x.end<y.end;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i].st>>a[i].end;
}
for(int i=1;i<=m;i++)
{
cin>>pos[i];
}
sort(a+1,a+1+n,cmp);
sort(pos+1,pos+1+m);
int l = 0;
last_pos = -0x3f3f3f;
for(int i=1;i<=n;i++)
{
if(a[i].st<=last_pos&&last_pos<=a[i].end&&i!=1) continue;
cnt++;
l++;//不重复选,虽然不加也不会重复选(因为排序),但可以节省几乎没有的时间复杂度
int r = m+1;
while(r-l>1)
{
int mid = (l+r)>>1;
if(pos[mid]<=a[i].end) l = mid;
else r = mid;
}
last_pos = pos[l];
}
cout<<cnt;
return 0;
}
问 AI ,AI说代码有问题却给不出 hack 数据,希望大家能帮忙出以下 hack 数据
回复
共 6 条回复,欢迎继续交流。
正在加载回复...