【AtCoder】AGC011 B. Colorful Creatures

AtCoderの問題

B: Colorful Creatures - AtCoder Grand Contest 011 | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ（初心者目線）

・考え方***

・実装**

・面白さ***

問題概要

・N匹の生き物がいる
・それぞれ大きさがAiで色がiである
・この生き物は自分の大きさの2倍以下の生き物を吸収できる
・例えば大きさA色aの生き物が大きさB色bの生き物を吸収したら
・大きさA+B色aの生き物になる
・N匹の生き物が1匹になるまで吸収を繰り返した時ありえる色のパターンは？

方針

・小さい生き物からその生き物の色を最後まで残せるかどうか調べた
・昇順にソートした時、「生き物jまで合体生物の大きさの2倍>=生物j+1の大きさ」なら生き物jまでの色は残せるし生き物j+1の色も残せる
・「生き物jまでの合体生物の大きさの2倍<=生き物j+1の大きさ」なら生き物j+1の色しか残せない

吸収したらソートし直したほうがいいと思ったけどしないでACになった…
いいのかな?

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int main(){
    int N;
    cin >> N;
    vector<double> A(N);
    FOR(i, 0, N) cin >> A[i];
    sort(A.begin(), A.end());
    ll ans = 1;
    FOR(i, 0, N-1){
        //どっちにもなれるなら色の可能性+1
        if(A[i+1] <= A[i] * 2){
            ans++;
        }
        //片方にしかなれないなら色の可能性は1になっちゃう
        else ans = 1;
        A[i+1] += A[i];
        //sortすべき??
    }
    cout << ans << endl;
}