丶xiaoHai
2019-10-09 15:34
采纳率: 96.8%
浏览 216

关于算法的一个小问题

题目和我的解在下面我的思路是定义一个数组将该线段之内的点全部置为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;
}
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • importantrubbish 2019-10-09 16:13
    已采纳

    题目描述形成一个“一一匹配”。楼主这个思路是在判断所有点是否都落在线段内。是不是没有考虑每条线段也都要有点。

    已采纳该答案
    打赏 评论

相关推荐 更多相似问题