求助3760贴海报

P3740 [HAOI2014] 贴海报

Xffishr @ 2023-10-09 23:58:55

这个代码前4个测试点没过,请问有什么问题吗谢谢

#include<bits/stdc++.h>
using namespace std;
const int Inf=9999999;
int n,m;
int a[Inf],b[Inf];
long long  d[Inf],ddd,c[Inf],ccc;
int book[Inf];
int kkk=1;
int main(){

    //离散化 
    cin>>n>>m;
    if(n==0||m==0)cout<<0<<endl;
    else{
            for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
        d[++ddd]=a[i];
        d[++ddd]=b[i];
    }
    //去重
    sort(d+1,d+1+ddd);
    c[++ccc]=d[1];
    for(int i=2;i<=ddd;i++){
        if(d[i-1]!=d[i])c[++ccc]=d[i];
    } 
    for(int i=1;i<=m;i++){
        int x=lower_bound(c+1,c+1+ccc,a[i])-c;
        int y=lower_bound(c+1,c+1+ccc,b[i])-c;
        for(int j=x;j<=y;j++){
            book[j]=i;
        }
    }
    sort(book+1,book+1+ccc);
    for(int i=2;i<=ccc;i++){
        if(book[i-1]!=book[i])++kkk;
    }
    cout<<kkk;
    }

    return 0;
}

by uzi_showmaker @ 2023-10-10 07:34:05

离散化对于本来有间隔的变成了紧挨着的情况,考虑将每一个端点 x+1 也加入离散化数组。


by Xffishr @ 2023-10-10 11:45:57

@uzi_showmaker 非常感谢,我去试试! 祝您一帆风顺


by Xffishr @ 2023-10-10 11:49:05

@uzi_showmaker

谢谢你!终于通过了哈哈哈哈哈哈


by uzi_showmaker @ 2023-10-10 12:01:04

不用谢,但是我并不顺风,刚才的考试爆0


by Xffishr @ 2023-10-15 19:08:19

@uzi_showmaker @uzi_showmaker 好运锦鲤


by TerryHan_Su @ 2023-12-23 19:53:44

@uzi_showmaker

谢谢你!终于通过了


by Jim_Franklin @ 2024-02-06 08:34:07

@uzi_showmaker 有点不太理解为什么一定要加进去


|