Cod sursa(job #923245)

Utilizator sebii_cSebastian Claici sebii_c Data 23 martie 2013 13:00:31
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>

#include <queue>
#include <vector>

using namespace std;

priority_queue<pair<double, double>, vector<pair<double, double> > > pq;

const int MAXN = 100001;
const double EPS = 1e-6;

double A, B;
double need;
double sum = 0.0;
double dist[MAXN];

void solve()
{
    int cnt = 0;
    while (sum - need > EPS) {
        double diff = pq.top().first;
        double curr = pq.top().second;
        pq.pop();
        ++cnt;

        sum -= diff;
        curr = curr - diff;
        diff = curr - B * curr;
        pq.push(make_pair(diff, curr));
    }

    printf("%d\n", cnt);
}

int main()
{
    freopen("minim2.in", "r", stdin);
    freopen("minim2.out", "w", stdout);

    int N;
    scanf("%d", &N);

    for (int i = 0; i < N; ++i) {
        scanf("%lf", &dist[i]);
        sum += dist[i];
    }

    scanf("%lf %lf %lf", &A, &B, &need);
    for (int i = 0; i < N; ++i) {
        double diff = dist[i] - A * dist[i];
        pq.push(make_pair(diff, dist[i]));
    }
    solve();

    return 0;
}