燃料分配问题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;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧