[HDU 3177]욕심
5275 단어 HDU
제목:용적 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 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.