단순 전형 적 인 욕심-(문제 풀이 보고서)HDU 2037--올해 여름 방학 은 AC 가 아 닙 니 다.

3737 단어 욕심HDU 물 문제
올 여름 방학 은 AC 가 아 닙 니 다.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 38863 Accepted Submission(s): 20780
문제 설명"올해 여름 방학 은 AC 가 아 닙 니까?""그렇다"고 말 했다."그럼 뭐 하 세 요?"월 드 컵 봐,바보 야!"@#$%^&*%..."
확실히 월 드 컵 이 오고 팬 들 의 명절 도 왔 으 니 많은 ACMer 도 컴퓨터 를 버 리 고 TV 로 달 려 갈 것 으로 보인다.팬 으로서 가능 한 한 많은 완전한 경 기 를 보고 싶 습 니 다.물론 새로운 시대 의 좋 은 청년 으로서 당신 은 반드시 다른 프로그램 을 볼 것 입 니 다.예 를 들 어 뉴스 연합 방송(국가 대사 에 관심 을 가 지 는 것 을 영원히 잊 지 마 세 요),매우 6+7,슈퍼 여자,그리고 왕 씨 가장귀 의 등 입 니 다.만약 에 당신 이 좋아 하 는 모든 텔레비전 프로그램의 중계 시간 표를 알 고 있다 고 가정 하면당신 은 합 리 적 으로 안배 할 수 있 습 니까?목 표 는 최대한 많은 프로그램 을 볼 수 있 도록 하 는 것 이다)
Input 입력 데 이 터 는 여러 개의 테스트 인 스 턴 스 를 포함 합 니 다.각 테스트 인 스 턴 스 의 첫 줄 은 하나의 정수 n(n<=100)만 있 습 니 다.좋아 하 는 프로그램의 총 수 를 나타 내 고 그 다음 에 n 줄 데이터 입 니 다.줄 마다 두 개의 데이터 Ti 가 포함 되 어 있 습 니 다.s,Ti_e(1<=i<=n)는 각각 i 번 째 프로그램의 시작 과 끝 시간 을 나타 내 고 문 제 를 간소화 하기 위해 시간 마다 하나의 정수 로 표시 한다.n=0 은 입력 이 끝 났 음 을 표시 하고 처리 하지 않 습 니 다.
Output 은 모든 테스트 인 스 턴 스 에 대해 전체 적 으로 볼 수 있 는 텔레비전 프로그램의 개 수 를 출력 하고 모든 테스트 인 스 턴 스 의 출력 은 한 줄 을 차지한다.
Sample Input 12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0
Sample Output 5
문제 풀이 사고:이 문 제 는 간단 한 욕심 사상 으로 이해 할 수 있 고 현재 의 최 적 화 를 매번 의 선택 으로 풀 수 있다.물론 이 문 제 는 각 프로그램의 종료 시간 을 먼저 오름차 순 으로 정렬 한 다음 에 그 핵심 적 인 절 차 는 다음 과 같다.먼저 종료 시간 이 가장 빠 른 프로그램 을 첫 번 째 프로그램 으로 묵인 한 다음 에 종료 시간 과 그 다음 에 종료 시간 이 두 번 째 빠 른 프로그램의 시작 시간 을 비교 하 는 것 이다.만약 에 이 시작 시간 이 종료 시간 보다 빠 르 면 이 프로그램 이 완전 하지 않다 는 것 을 의미한다.그래서 시작 시간 이 늦 어 질 때 까지 첫 번 째 전체 프로그램 을 뒤로 찾 았 다.그리고 계속 밀어.구체 적 인 코드 는 다음 과 같다.
#include 
#include 
#include 
using namespace std;
const int N=105;

typedef struct data
{
    int s;
    int e;
}data;

int cmp(data x,data y)
{
    return x.e//                   ! 
 } 
int main()
{
    int n;
    data a[N];
    while(cin>>n&&n)
    {
        int k=0,sum=1;
        memset(a,0,sizeof(a));
        for(int i=0;icin>>a[i].s>>a[i].e;
        }
        sort(a,a+n,cmp);
        for(int i=0;i//    ,                   ,                              ,                        ,                     。 
        {
            if(a[k].e<=a[i].s)
            {
                sum++;
                k=i;
            }
        }
        cout<return 0; 
    }

개인 적 인 관점 만 을 대표 합 니 다.뿌 려 서 는 안 됩 니 다.교 류 를 환영 합 니 다!!

좋은 웹페이지 즐겨찾기