Cod sursa(job #2096004)

Utilizator giotoPopescu Ioan gioto Data 28 decembrie 2017 14:23:32
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;

int n;
double l[100005];
double a, b, r;
const int eps = 1e-6;
struct usu{
    double x;
    int y;
    bool operator < (const usu &aux) const{
        return x < aux.x;
    }
};
priority_queue <usu> pq;
int main()
{
    freopen("minim2.in", "r", stdin);
    freopen("minim2.out", "w", stdout);
    scanf("%d", &n);
    long double Sum = 0;
    int x;
    for(int i = 1; i <= n ; ++i){
        scanf("%d", &x);
        l[i] = x;
        Sum += l[i];
    }
    scanf("%lf%lf%lf", &a, &b, &r);
    for(int i = 1; i <= n ; ++i)
        pq.push({l[i] - (double)l[i] * a, i});
    int NR = 0;
    while(Sum > r && abs(Sum - r) > eps){
        Sum = Sum - pq.top().x;
        int pos = pq.top().y;
        l[pos] -= pq.top().x;
        pq.pop();
        pq.push({l[pos] - (double)l[pos] * b, pos});
        ++NR;
    }
    printf("%d", NR);
    return 0;
}