燃料分配问题C++贪心算法

考虑贪心，我们应该让尽可能多地机器进行工作，如果把燃料全部投入到少数几个机器上，那么很容易到达上限。而燃料越分散，则越不容易达到上限。

#include
#include
#define ll long long
using namespace std;
ll n, m, k, q, t, f1, n1, f2, n2, ans;
int main() {
scanf("%lld%lld%lld%lld%lld", &n, &m, &k, &q, &t);
if (m < k) {
printf("0");
return 0;
}
if (n * k > m) n = m / k;//如果有不能启动的，那么只启动可以启动的
m -= n * k;//减去启动消耗
if (m % n) {//如果不能平分剩下的
f2 = k + m / n + 1;//f2分多1个
n2 = m % n;//人数
}
f1 = k + m / n;
n1 = n - n2;
ans += min(f1 * t, q) * n1;
ans += min(f2 * t, q) * n2;
printf("%lld", ans);
return 0;
}

#include
using namespace std;
#define ll long long
const int maxn = 5e5 + 10;
const int inf = 0x3f3f3f3f;
ll n, ans, num[maxn];
int nxt[maxn][5];
int startpos, endpos;
// -2 --> 0 // -1 --> 1
// 1 --> 3  // 2 --> 4
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    memset(nxt, 0x3f, sizeof nxt);
    for(int i = 1;i <= n; ++i) {
        cin >> num[i];
    }
    ll ret = 1, lst = num[1];
    for(int i = 2;i <= n; ++i) {
        if(num[i] == lst) ++ret;
        else {
            ans += ret * (ret + 1) / 2;
            ret = 1; lst = num[i];
        }
    }
    ans += ret * (ret + 1) / 2;
    for(int i = n;i >= 1; --i) {
        for(int j = 0;j <= 4; ++j) nxt[i][j] = nxt[i + 1][j];
        nxt[i][num[i] + 2] = i;
        int maxpos1 = nxt[i][1 + 2], maxpos2 = nxt[i][2 + 2];
        int minpos1 = nxt[i][-1 + 2], minpos2 = nxt[i][-2 + 2];
        startpos = max(maxpos2, minpos2); endpos = n + 1;
        if(startpos != inf && startpos < endpos) ans += endpos - startpos;
        startpos = max(maxpos1, minpos1); endpos = min(min(maxpos2, minpos2), (int)n + 1);
        if(startpos != inf && startpos < endpos) ans += endpos - startpos;
    }
    cout << ans << 'n';
    return 0;
}