问题标题: 酷町堂：1413 区间选点

Question

0

已解决

李素妍

新手天翼

50分

#include <iostream>

#include <algorithm>

using namespace std;

struct w{

int x,y;

}a[110];

bool cmp(w a,w b){

if(a.x!=b.y)return a.x<b.y;

return a.y<b.y;

}

int main(){

int n,cnt=0;

cin>>n;

for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;

sort(a+1,a+1+n,cmp);

for(int i=1;i<n;i++){

if(a[i].y<a[i+1].x){

cnt++;

}

cout<<cnt+1;

return 0;

}

李素妍在2021-03-10 21:36:16追加了内容

1

Answer 1

已采纳

陈曦

资深天翼

你不是做出来了吗

Answer 2

陈正朔

初级光能

排序规则改一下

if(a.y!=b,y) return a.y<b.y;
return a.x<b.x;

第二个循环改成

int end=-1;
    for(int i=1;i<=n;i++){
        if(a[i].x>end){
            end=a[i].y;
            cnt++;
        }
    }

最后输出cnt

Answer 3

张帆

中级天翼

cmp函数：

bool cmp(qj a,qj b){
    return a.l<b.l;
}

最后

 tmp=a[1];
    for(int i=2;i<=n;i++){
        if(a[i].l<=tmp.r){
            tmp.l=a[i].l;
            tmp.r=min(tmp.r,a[i].r);
        } else {
            ans++;
            tmp=a[i];
        }
    }
    cout<<ans;

PS：变量名有些不符，是我的代码里面的，请改一下哈。

问题标题: 酷町堂：1413 区间选点

3 个回答: