w-haiS 2019-10-09 15:34 采纳率: 64.3%
浏览 230
已采纳

关于算法的一个小问题

题目和我的解在下面我的思路是定义一个数组将该线段之内的点全部置为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
    关注

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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥20 关于#硬件工程#的问题,请各位专家解答!
  • ¥15 关于#matlab#的问题:期望的系统闭环传递函数为G(s)=wn^2/s^2+2¢wn+wn^2阻尼系数¢=0.707,使系统具有较小的超调量
  • ¥15 FLUENT如何实现在堆积颗粒的上表面加载高斯热源
  • ¥30 截图中的mathematics程序转换成matlab
  • ¥15 动力学代码报错,维度不匹配
  • ¥15 Power query添加列问题
  • ¥50 Kubernetes&Fission&Eleasticsearch
  • ¥15 報錯:Person is not mapped,如何解決?
  • ¥15 c++头文件不能识别CDialog
  • ¥15 Excel发现不可读取的内容