题目和我的解在下面我的思路是定义一个数组将该线段之内的点全部置为1;到最后在判定数组中所有对应的点是不是为1,但是这样样例通过率只为50,有什么错误请大老看一下
谢谢。
题目描述
给你坐标轴上的n个点,和n条线段,能否找到一种配对方案使得点与线段之间能形成一一匹配,一个匹配的定义是点在线段内
输入描述:
第一行输入一个整数n (1 ≤ n ≤ 100)
第二行输入n个整数p[i]
第三行输入n个整数l[i]
第三行输入n个整数r[i]
p[i]表示第i个点的位置,l[i],r[i] 表示第i条线段的左右端点
-500 ≤ p[i], l[i], r[i] ≤ 500
输出描述:
如果能找到配对方案,输出"Possible"
否则输出"Impossible"
示例1
输入
2
1 2
0 0
1 3
输出
Possible
示例2
输入
1
0
2
3
输出
Impossible
示例3
输入
3
0 1 2
0 0 1
1 2 1
输出
Possible
备注:
子任务1:n <= 20
子任务2:n <= 50
子任务3:无限制
下面是我的代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
int p[101];
int l[101],r[101];
int judge[1002];
memset(judge,0,sizeof(int)*1002);
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i];
}
for(int i=1;i<=n;i++)
cin>>l[i];
for(int i=1;i<=n;i++)
cin>>r[i];
for(int i=1;i<=n;i++){
for(int j=l[i]+500;j<=r[i]+500;j++){
judge[j] = 1;
}
}
for(int i=1;i<=n;i++){
if(judge[(p[i]+500)]==0){
cout<<"Impossible"<<endl;
return 0;
}
}
cout<<"Possible"<<endl;
return 0;
}