탐욕 알고리즘 - 국왕 게임 (로 곡 P1080)

탐욕 알고리즘 - 왕 게임
제목 설명
문제 분석
알고리즘 소스 코드
1. 제목 설명
제목 묘 사 는 마침 H 개국 국경일 에 왕 이 n 명의 대신 을 초청 하여 유상 게임 을 하 게 하 였 다.우선, 그 는 모든 대신 에 게 왼쪽, 오른손 에 각각 정 수 를 쓰 라 고 했 고 왕 자신 도 왼쪽, 오른손 에 각각 정 수 를 썼 다.그리고 이 n 명의 대신 을 일렬 로 세우 고 왕 은 대열 의 맨 앞 에 섰 다.줄 을 서 면 모든 대신 들 이 왕 에 게 상 을 주 는 몇 개의 금 화 를 받는다. 모든 대신 들 이 받 은 금 화 는 각각 이 대신 앞 에 있 는 모든 사람의 왼손 에 있 는 곱 하기 를 자신의 오른손 에 있 는 숫자 로 나 눈 다음 에 아래로 정리 한 결과 이다.
왕 은 어떤 대신 이 특별히 많은 상 을 받 기 를 원 하지 않 았 습 니 다. 그래서 그 는 당신 에 게 팀 의 순 서 를 다시 짜 서 가장 많은 상 을 받 은 대신 들 이 가능 한 한 적은 상 을 받 도록 도와 달라 고 부탁 하고 싶 었 습 니 다.주의 하 세 요. 왕 의 위 치 는 항상 대열 의 맨 앞 에 있 습 니 다.
형식 첫 줄 에 정수 n 을 포함 하여 대신 수 를 표시 합 니 다.
두 번 째 줄 은 두 개의 정수 a 와 b 를 포함 하고 그 사 이 를 빈 칸 으로 나 누 어 각각 왕 의 왼손 과 오른손 의 정 수 를 나타 낸다.
다음 n 줄 은 각 줄 에 두 개의 정수 a 와 b 를 포함 하고 사 이 를 하나의 빈 칸 으로 나 누 어 각 대신 들 의 왼손 과 오른손 의 정 수 를 나타 낸다.
출력 형식 은 하나의 정수 로 재 배열 한 파티 에서 가장 많은 상 을 받 은 대신 이 받 은 금화 수 를 나타 낸다.
입 출력 샘플 입력 \ # 1 복사 3 1 1 2 3 7 4 6 출력 \ # 1 복사 2 설명 / 알림 [입 출력 샘플 설명]
1, 2, 3 으로 줄 을 서서 상 을 가장 많이 받 은 대신 이 받 은 금화 수 는 2 이다.
1, 3, 2 로 줄 을 서서 상 을 가장 많이 받 은 대신 이 받 은 금화 수 는 2 이다.
2, 1, 3 으로 줄 을 서서 상 을 가장 많이 받 은 대신 이 받 은 금화 수 는 2 이다.
2, 3, 1 로 줄 을 서서 상 을 가장 많이 받 은 대신 이 받 은 금화 수 는 9 이다.
3, 1, 2 로 줄 을 서서 상 을 가장 많이 받 은 대신 이 받 은 금화 수 는 2 이다.
3, 2, 1 로 줄 을 서서 상 을 가장 많이 받 은 대신 이 받 은 금화 수 는 9 이다.
이에 따라 가장 많은 상 을 주 는 대신 은 최소 2 개의 금 화 를 받 고, 정 답 은 2 를 수출 한다.
【 데이터 범위 】
20% 의 데이터 에 대해 1 ≤ n ≤ 10, 0 < a, b < 8;
40% 의 데이터 에 대해 1 ≤ n ≤ 20, 0 < a, b < 8;
60% 의 데이터 에 대해 1 ≤ n ≤ 10;
60% 의 데이터 에 대해 답 이 10 ^ 9 를 초과 하지 않도록 보증 합 니 다.
100% 의 데이터 에 대하 여 1 ≤ n ≤ 1, 000, 0 < a, b < 10000.
NOIP 2012 향상 팀 첫날 2 번 문제.
2. 문제 분석
먼저 수학 사상 을 이용 하여 모델 링 을 하고 문제 의 일반화 형식 을 표시 한 다음 에 일반화 형식 에 따라 분석 하여 전체 화 된 문 제 를 분석한다.
제 i 개 대신 들 의 수익 은 ci 이 고 왼손 금액 은 ai 이 며 오른손 금액 은 bi 이 며 제 j 개 대신 들 의 수익 은 cj 이 며 왼손 금액 외 aj 이 고 오른손 금액 은 bj 이 며 제 i 개 대신 전 i - 1 명 (첫 번 째 고정 적 인 왕 과 전 i - 2 개 대신 포함) 의 금액 의 합 은 x 이다.

                                            
    i-1                x            /
    i                 ai           bi
    j                 aj           bj

제목 의 요구 에 따라 ci = x / bi, cj = x * ai / bj 가 있 습 니 다.
이때 두 대신의 비교적 큰 수익 을 C1 로 기록 하면 C1 = max {x / bi, x * ai / bj}
우 리 는 배열 방식 이 전체 최대 수익 에 미 치 는 영향 을 연구 해 야 하기 때문에 i 번 째 대신 과 j 번 째 대신 의 배열 을 바 꿔 야 한다.

                                            
    i-1                x            /
    j                 aj           bj
    i                 ai           bi

제목 의 요구 에 따라 ci = x * aj / bi, cj = x / bj 가 있 습 니 다.
이때 두 대신의 비교적 큰 수익 은 C2 로 기록 하면 C2 = max {x * aj / bi, x / bj}
(1) 、 C1 을 C1 로 설정 하고 C2 중의 작은 자 는 C1 < = C2 가 있 습 니 다.
즉 max {x / bi, x * ai / bj} < = max {x * aj / bi, x / bj}
x, ai, bi, aj, bj 는 모두 0 보다 큰 정수 이기 때문이다.
x/bi <= x* aj/ bi , x*ai/bj>=x/bj
설정 k1 = x / bi, k2 = x * ai / bj, k3 = x * aj / bi, k4 = x / bj
k1 < = k3, k2 > = k4
max {k1, k2} < = max {k3, k4} 을 만 들 기 위해 서 는 k2 < = k3 이 있 습 니 다.
즉 x * ai / bj < = x * aj / bi, 정리 한 ai * bi < = aj * bj
(2) 、 C2 를 C1 로 설정 하고 C2 중의 작은 자 는 C1 > = C2 가 있 습 니 다.
즉 max {x / bi, x * ai / bj} > = max {x * aj / bi, x / bj}
x, ai, bi, aj, bj 는 모두 0 보다 큰 정수 이기 때문이다.
x/bi <= x* aj/ bi , x*ai/bj>=x/bj
설정 k1 = x / bi, k2 = x * ai / bj, k3 = x * aj / bi, k4 = x / bj
k1 < = k3, k2 > = k4
max {k1, k2} > = max {k3, k4} 을 만 들 기 위해 서 는 k3 < = k2 가 있 습 니 다.
즉 x * aj / bi < = x * ai / bj, 정리 한 aj * bj < = ai * bi
다시 말하자면 대신 중에서 비교적 큰 수익 을 얻 는 사람의 수익 이 비교적 적 게 하기 위해 임의로 인접 한 두 대신 i 와 j 에 대해 모두 관계 식 ai * bi < = aj * bj 를 만족 시 키 고 좌우 금액 의 수량 에 따라 순 위 를 곱 하면 된다.
(단, 곱셈 연산 을 할 때 는 곱셈 과정 에서 수치 가 정상 데이터 의 표시 범 위 를 초과 하면 높 은 정밀도 알고리즘 으로 프로그램 을 작성 하 십시오)
3. 알고리즘 소스 코드

#include
#define ll long long
using namespace std;
int n;
int len = 1;//          
int sum[100001] = {0,1};//          
struct minister{
	ll left;
	ll right;
} m[1000001];
bool cmp(minister a,minister b){
	return a.left * a.right < b.left * b.right;
}
void multiplicative(ll x){//      
	for(int i = 1;i <= len; i++){
		sum[i] *= x; //    x, 1111×20 = (1000+100+10+1)×20 
	} 
	for(int i = 1;i <= len; i++){
		sum[i + 1] += sum[i] / 10;//    ,          10 3 13 4,     1 0 4 3 4
		sum[i] %= 10;
	}
	len++;//   sum[i+1],        sum[len+1],    len++
	while(sum[len] / 10){//          ,                 100 3     
		sum[len + 1] = sum[len] / 10;
		sum[len] %= 10;
		len++; 
	} 
    //          ,       sum[len]     0,  0     
	if(sum[len] == 0)
	len--; 
}
void division(){//     ,           ,        
	//       , 2345/5=(2000+300+40+5)/5,      
	//->2 3 4 5 ->0 23(3 + 2%5*10) 4 5 -> 0 4 34(4 + 23%5*10) 5 -> 0 4 6 45(5 + 34%5*10)
	for(int i = len; i >= 1; i--){
		sum[i - 1] += (sum[i] % m[n].right * 10);
		sum[i] /= m[n].right;
	}
	//            0，    
	while(!sum[len]){
		len--;
	}
	//     
	if(len == 0) cout << "1" << endl; 
} 
int main(){
	cin >> n;
    cin >> m[0].left >> m[0].right;
	for(int i = 1;i <= n; i++)
	cin >> m[i].left >> m[i].right;
	sort(m + 1, m + 1 + n, cmp);
	for(int i = 0;i < n; i++){
		multiplicative(m[i].left); 
	}
	division();
	for(int i = len; i >= 1; i--)
	cout << sum[i];
	
}