2018 Codem 퀄 리 파 잉 콜라

[프로 그래 밍 | 1000 점] 콜라.
시간 제한: C / C + + 1 초, 기타 언어 2 초
공간 제한: C / C + + 262144 K, 기타 언어 524288 K
제목 설명
소 미 와 소 단 은 최근 에 콜라 에 푹 빠 졌 다.TA 들 이 선택 할 수 있 는 콜 라 는 모두 k 가지 가 있 는데 예 를 들 어 코카콜라, 0 도 콜라 등 이다. 모든 콜 라 는 작은 아름다움 과 작은 덩어리 에 서로 다른 즐거움 을 줄 수 있다.
TA 들 은 모두 n 병 의 콜 라 를 사려 고 합 니 다. 각 콜 라 는 무한 여러 병 을 살 수 있 습 니 다. 소 미 는 그 중의 m 병 을 무 작위 로 골 라 마시고 나머지 n - m 병 은 단체 로 마 실 수 있 습 니 다.
콜 라 를 어떻게 구 매 하여 소 미 와 소 단 이 얻 는 즐거움 정도 와 기대 치 를 가장 크게 해 야 합 니까?
지금 콜 라 를 구 매 하 는 방안 을 요청 합 니 다.
입력 설명:

       n，m，k          、                  。
   k ，      a，b                      。
      ，1 <= n <= 10,000, 0 <= m <= n, 1 <= k <= 10,000, -10,000 <= a, b <= 10,000

출력 설명:

  k   ， i        i      。
     ，           。
       a1, a2, ..., ak, b1, b2, ..., bk，a      b，          i <= k  ：
ai < bi         j < i，aj = bj；

예시 1
입력

2 1 2
1 2
3 1

출력

0 2

설명 하 다.

         ：
1.  2      ，         ，           1+2=3；
2.  1       1      ，                     ，                ，           1*0.5+3*0.5+2*0.5+1*0.5=3.5；
3.  2      ，         ，           3+1=4。

제목: 소 미 와 소 단 은 콜라 n 잔, 소 미 는 m 잔, 소 단 과 n - m 잔 을 마셔 야 한다.콜라 n 잔 은 K 종 콜라 중에서 골 라 낸 것 으로 모든 콜 라 는 임의의 잔 을 선택 할 수 있다.사 온 n 잔 의 콜라 에 대해 샤 오미 와 작은 덩어리 는 모두 무 작위 로 고 른 것 이다. 즉, 이미 사 온 n 잔 의 콜라 중 한 잔 의 콜라 에 대해 샤 오미 가 마 실 확률 은?  m / n。작은 덩어리 가 마 실 확률 은...  （n-m）/n。모든 콜 라 를 마 시 면 소 미 와 소 단 에 게 서로 다른 즐거움 을 줄 수 있다. 소 미 와 소 단 이 기대 하 는 가장 큰 즐거움 을 얻 을 때 모든 콜라 의 선택 잔 수 는 얼마 입 니까?
사고방식: 콜라 한 잔 은 모두 무 작위 로 샤 오미 와 작은 단체 에 게 마 시 는 것 이기 때문에 이미 사 온 콜라 한 잔 에 대해  소 미 에 게 주 는 속도 가 빠르다 고 가정 하면 a 가 소 단 에 게 주 는 즐거움 정도 가설 은?  b. 그러면 이 콜라 가 작은 아름다움 과 작은 단체 에 게 주 는 기대 즐거움 정 도 는 (m / n) * a + (n - m) / n) * b 입 니 다.k 가지 콜 라 는 모든 종류 가 임의의 잔 을 살 수 있 기 때문에 기대 즐거움 이 가장 큰 콜 라 를 사고 n 잔 을 사 야 합 니 다!!하지만!!!다양한 콜라 가 같은 즐거움 을 기대 합 니 다!!그럼 사전 순 서 를 최소 로 출력 하려 면 가장 뒤쪽 에 있 는 콜라 만 사면 됩 니 다!!
코드 는 다음 과 같 습 니 다:

#include 
#include 
#include 

using namespace std;
const int maxn = 1e4+100;
int n,m,k;
int a[maxn],b[maxn];
const int inf = 1e9;
int G[maxn];
int main(){
    while(~scanf("%d%d%d",&n,&m,&k)){
        for(int i=1;i<=k;i++){
            scanf("%d %d",&a[i],&b[i]);
        }

        int index;
        double p = 1.0*m/n;
        double ans = p * a[1] + (1.0-p)*b[1];
        for(int i=1;i<=k;i++){
            double curren = p * a[i] + (1.0-p)*b[i];
            if(curren >= ans){
                ans = curren;
                index = i;
            }
        }
      

        for(int i=1;i<=k;i++){
            if(i==index){

                printf("%d%c",n,i==k?'
':' ');
            }
            else{
                printf("%d%c",0,i==k?'
':' ');
            }
        }
    }
    return 0;
}