社区讨论

求判断代码是否正确

学术版参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mhizxni9
此快照首次捕获于
2025/11/03 18:27
4 个月前
此快照最后确认于
2025/11/03 18:27
4 个月前
查看原帖
这是自己写的代码,题目也是自己给的,而题目大概是这样的
给出 nn 个区间的起点终点,并且给出 mm 个点的位,要求从 mm 个点中选最少数量的点以达到每个区间至少覆盖了一个点的目标

输入格式

第一行:两个正整数, nnmm
接下来 nn 行:每行两个非负数,其中第 ii 行表示第 ii 个区间的起点终点
接下来一行: mm 个非负数,其中第 jj 个表示第 jj 个点的坐标

输出格式

一行,表示至少选几个点

时空限制

满足 n105n\le 10^5m105m\le 10^5

我的代码

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 条回复,欢迎继续交流。

正在加载回复...