POJ 2393 贪心

    xiaoxiao2021-03-25  277

    贪心

    每个星期可以制作无限数量的酸奶,每个星期有一个客户酸奶需求量Yi和单位酸奶制作花费Ci,酸奶可以以每个星期每单位S的花费无限储存。问如何花费最少满足所有客户需求量。

    第i个星期若采用前面第j个星期时制作的酸奶,需满足式子

    Ci * Yi > Cj * Yi + S * Yi * (i - j)

    Ci - Si > Cj - Sj

    维护一个nowleast为当前星期前Cx - Sx的最小值以及那个星期编号num,更新ans。

    #include <cstdio> #include <cstdlib> #include <iostream> #include <cmath> #define Maxn 10000 using namespace std; int n , s; long long ans; int c[Maxn + 10], y[Maxn + 10]; int nowleast, num; int main() { scanf("%d%d", &n, &s); nowleast = -1; for (int i = 1;i <= n;++ i) { scanf("%d%d", &c[i], &y[i]); if (nowleast == -1 || nowleast >= c[i] - s * i ) { nowleast = c[i] - s * i; num = i; ans = ans + c[i] * y[i]; //printf("change to %d : num %d\nans : %lld\n", nowleast, num, ans); } else { ans = ans + c[num] * y[i] + s * (i - num) * y[i]; //printf("use nowleast %d : num %d\nans : %lld\n", nowleast, num, ans); } } printf("%lld\n", ans); return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-163.html

    最新回复(0)