程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 九度OJ 1463 招聘會

九度OJ 1463 招聘會

編輯:關於C++

這個題目是典型的貪心問題。貪心策略如下:按照結束時間進行從小到大排序,從第一個開始遍歷排序後的招聘會一遍得出結果,每次設置一個temp進行記錄當前所在招聘會,下一個招聘會向後找到第一個不沖突的,然後修改temp,當然此時能參加的招聘會要+1。

貪心策略簡單證明:假設有兩個招聘會A和B,且A的結束時間要早於B的結束時間,那麼顯然我們選擇B的時候B的所有後續安排全部不會和A沖突,而選擇A的時候A的後續卻不一定滿足不與B沖突。一個直觀的理解就是越早完成的招聘會會給後續招聘會騰出更多時間。

貼代碼,注意題目描述有點瑕疵,輸入並不止一組。

#include
#include
using namespace std;
struct node{
    int start;
    int end;
};
bool cmp(node a,node b)
{
    if(a.end<=b.end)
        return true;
    return false;
}
node act[10050];
int main()
{
    int n,i;
    while(cin>>n)
    {
        for(i=1;i<=n;i++)
            cin>>act[i].start>>act[i].end;
        sort(act+1,act+1+n,cmp);
        int temp=1;
        int sum=1;
        for(i=2;i<=n;i++)
        {
            if(act[i].start>=act[temp].end)
            {
                temp=i;
                sum=sum+1;
            }
        }
        cout<

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved