Cod sursa(job #961363)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 22:26:53
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 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;
}