Change-free (codeforces 767E)

タイトルリンク:[http://codeforces.com/contest/767/problem/E]
分析:
できるだけコインを交換しないでこそ、代価を最小限に抑えることができるに違いない.i日目まで硬貨の数が支払いに足りない場合は、1日目からi日目までの中で、最も代価の少ない日を選んで収容員にお釣りをさせるべきです.いずれの日に硬貨を獲得しても硬貨数は+100であることが分かるが,毎日の代価は異なり,(100−ci%100)−wi(100−c i%100)−w iを優先キューに入れ,最小代価を取り出すたびによい.具体的な実装はコードを参照
ACコード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

const int maxn = 1e5+100;
struct node
{
    int w,id;
    node (int value = 0, int ID = 0)
    {
        w = value, id = ID;
    }
    friend bool operator < (const node &a,const node &b)
    {
        return a.w>b.w;
    }
};
int n,x,c[maxn],w[maxn];
bool f[maxn];

void solve()
{
    long long ans = 0;

    priority_queue  Q;
    for (int i=0;iif (c[i] % 100 == 0)  continue;
        int v = (100-c[i]%100) * w[i];
        Q.push(node(v,i));

        while (x < c[i]%100)
        {
            ans += Q.top().w;
            f[Q.top().id] = true;
            x += 100;
            Q.pop();
        }  
        x -= c[i]%100;
    }

    printf("%I64d
",ans);
    for (int i=0;iif (f[i]) 
            printf("%d 0
",c[i]/100+1);
        else
            printf("%d %d
",c[i]/100,c[i]%100);
    }
    return;
}

int main()
{
    scanf("%d %d",&n,&x);
    for (int i=0;i"%d",&c[i]);
    for (int i=0;i"%d",&w[i]);
    solve();
    return 0;
}