HDOJ. 1051 나무 스틱 (욕심)

Wooden Sticks
도전 문 제 를 눌 러 주세요.
제목 분석
T 조 의 데 이 터 를 보 여 줍 니 다. 각 조 의 데 이 터 는 n 대수 가 있 고 각각 나무 막대기 의 길이 l 과 무게 w 를 대표 합 니 다.첫 번 째 나무 막대 가공 은 1min 의 준비 시간 이 필요 합 니 다. 방금 가공 한 나무 막대 에 대해 다음 나무 막대 l 과 w 가 모두 이전 나무 막대 의 l 과 w 보다 작 으 면 준비 시간 이 필요 하지 않 습 니 다. 그렇지 않 으 면 1min 의 준비 시간 이 필요 합 니 다.각 그룹의 데이터 에 필요 한 최소 준비 시간 이 얼마 인지 알 아 보 세 요.탐욕의 책략.나무 막대 에 대해 내림차 순 서 를 매기 는데 가장 중요 한 키 워드 는 l 이 고 부차적인 키 워드 는 w (거꾸로 할 수 있다) 이다.그 다음 에 맨 위 에 있 는 나무 막대 기 를 선택 하여 아래로 옮 겨 다 닙 니 다. 현재 나무 막대 에 대해 l 과 w 가 모두 꼭대기 에 있 는 나무 막대 보다 작 으 면 처 리 된 것 으로 표시 하고 이때 나무 막대 의 데 이 터 를 업데이트 하여 나무 막대 가 알 수 없 을 때 까지 계속 옮 겨 다 닙 니 다.이때 모든 나무 막대 가 처리 되 었 는 지 여 부 를 판단 합 니 다. 예, 출력 결 과 를 판단 합 니 다. 그렇지 않 으 면 꼭대기 에 처리 되 지 않 은 나무 막대 기 를 계속 선택 하여 반복 적 으로 반복 합 니 다.
코드 총람
/*
    Title:HDOJ.1051
    Author:pengwill
    Date:2016-11-25
*/
#include 
#include 
#include 
#define max 5005
using namespace std;
struct stick{
    int len;
    int weight;
    bool fish;
}item[max];
bool cmp(stick a,stick b)
{
    if(a.len == b.len){
        return a.weight>b.weight;
    }else{
        return a.len>b.len;
    }
}

int main()
{
    int t;
    //freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        int n,i;
        scanf("%d",&n);
        for(i = 0;iscanf("%d %d",&item[i].len,&item[i].weight);
        }
        sort(item,item+n,cmp);
        int num = 0,nlen,nweight,cnt = 0,temp= 0;
        while(num!= n){
            for(i = temp;iif(item[i].fish == false){
                    nlen = item[i].len;
                    nweight = item[i].weight;
                    item[i].fish = true;
                    num++;cnt++;i++;
                    temp = i;
                    break;
                }
            }
            for(;iif(item[i].fish == false && item[i].len<=nlen && item[i].weight<=nweight){
                        item[i].fish = true;
                        num++;
                        nlen = item[i].len;
                        nweight = item[i].weight;
                    }
            }
        }
        printf("%d
"
,cnt); for(i = 0;ifalse; } } return 0; //fclose(stdin); }

좋은 웹페이지 즐겨찾기