[HDU 3177]욕심

5275 단어 HDU
제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=3177
제목:용적 V 의 구멍 이 있 고 n 개의 물건 이 있다.모든 물건 은 실제 부피 와 이 물건 을 옮 기 는 데 필요 한 추가 부피 가 있 으 며,모든 물건 이 구멍 으로 옮 길 수 있 는 지 물 어보 세 요.
문제 풀이 방향:
제목 을 보면 욕심 이 연상 되 기 쉬 우 니 욕심 이 중요 하 다.처음에 생각 한 것 은 b 의 최대 순 서 를 따 르 고 b 가 같 으 면 a 의 최소 순 서 를 따 르 고 WS 를 발견 하 는 것 이 었 다.일반적으로 이런 문 제 를 만 나 하나의 정렬 로 통 하지 않 으 면 두 변수 간 의 가감 곱 하기 관 계 를 연상 한다.
이 문 제 는 a,b 간 의 차이 에 따라 정렬 하 는 것 이다.
 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 #include <algorithm>

 5 using namespace std;

 6 

 7 struct node

 8 {

 9     int  a, b;

10 }f[1024];

11 

12 bool cmp(node A, node B)

13 {

14     return A.b-A.a>B.b-B.a;

15 }

16 

17 int main()

18 {

19     int  T, n, V, i;

20     cin >> T;

21     while(T--)

22     {

23         scanf("%d%d",&V,&n);

24         for(i=0; i<n; i++)

25             scanf("%d%d",&f[i].a,&f[i].b);

26         sort(f,f+n,cmp);

27         for(i=0; i<n; i++)

28         {

29             if(V>=f[i].b)

30                 V-=f[i].a;

31             else break;

32         }

33         if(i==n)

34             cout << "Yes" << endl;

35         else

36             cout << "No" << endl;

37     }

38     return 0;

39 }

 
 
 
 
 
 
 

좋은 웹페이지 즐겨찾기