溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

【貪心算法】關于貪心的一些思考

發(fā)布時間：2020-08-07 05:56:11 來源：網(wǎng)絡 閱讀：555 作者：Rign 欄目：編程語言

貪心最主要的問題就是無后效性

當前最優(yōu)解就是全局最優(yōu)解

https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/2073.html

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct act{
    int start;
    int end;
}a[105];

int cmp(act a,act b){
    return a.end<b.end;
}

int main(){
    int n; 
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
        cin>>a[i].start>>a[i].end;
    }
    //printf("\n");
    sort(a+1,a+n+1,cmp);
    //for(int i=1;i<=n;i++){
    //  printf("%d %d\n",a[i].start,a[i].end);
    //}
    int i=1,sum=1;
    for(int j=2;j<=n;j++){
        if(a[j].start>=a[i].end){
            sum++;
            i=j;
        }
    }
    printf("%d\n",sum);
    }
    return 0;
}
向AI問一下細節(jié)

免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內(nèi)容。

AI
助
手