程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 貪心 HDU 3697

貪心 HDU 3697

編輯：C++入門知識

貪心 HDU 3697

因為時間是都是5分鐘增加的。所以我們可以從0開始到4每次都把可能的時間保存到一個數組裡。然後遍歷所有的情況

對於結構體的話，我們先按照結束的時間從小到大來排序，如果結束的時間相同，那麼就按照開始的時間從小到大來排序

最後在判斷的時間的時候就要一個閉區間一個開區間了。據說只要是時間判斷的話都要這樣的。

Selecting courses

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 62768/32768 K (Java/Others)
Total Submission(s): 1986 Accepted Submission(s): 504

Problem Description A new Semester is coming and students are troubling for selecting courses. Students select their course on the web course system. There are n courses, the ith course is available during the time interval (A_i,B_i). That means, if you want to select the ith course, you must select it after time Ai and before time Bi. Ai and Bi are all in minutes. A student can only try to select a course every 5 minutes, but he can start trying at any time, and try as many times as he wants. For example, if you start trying to select courses at 5 minutes 21 seconds, then you can make other tries at 10 minutes 21 seconds, 15 minutes 21 seconds,20 minutes 21 seconds… and so on. A student can’t select more than one course at the same time. It may happen that no course is available when a student is making a try to select a course

You are to find the maximum number of courses that a student can select.

Input There are no more than 100 test cases.

The first line of each test case contains an integer N. N is the number of courses (0
Then N lines follows. Each line contains two integers Ai and Bi (0<=A_ii<=1000), meaning that the ith course is available during the time interval (Ai,Bi).

The input ends by N = 0.

Output For each test case output a line containing an integer indicating the maximum number of courses that a student can select.

Sample Input

Sample Output

Source 2010 Asia Fuzhou Regional Contest

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define MAXN 300 + 10

struct node{
    int x;
    int y;
}a[MAXN];
int vis[MAXN];
int t[1111];

bool cmp(node a,node b){
    if(a.y == b.y){
        return a.x < b.x;
    }
    return a.y < b.y;
}

int Max(int a,int b){
    return a>b?a:b;
}

int main(){
    int n,i,j;
    int time;

    while(~scanf("%d",&n)){
        if(n == 0){
            break;
        }
        for(i=0;i mark){
                    break;
                }
                t[cnt] = flag;
                cnt++;
            }
            sum = 0;
            for(i=0;i=a[j].x && t[i]