時間限制
現在
數據範圍：
3 題解我們分析題目，發現：最終的答案與技能本身的順序無關，只與它們的具體值有關。因此，我們可以先對所有技能按照初始等級排序。
這道題要我們求的是某兩個值的和的最大值。雖然這道題看起來可以用
第一層循環，我們利用
4 代碼（空格警告）：#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
#define int long long
int n, A, cf, cm, m, Left, ans, alevel, ans1, ans2, aA;
int sum1[N], sum2[N];
struct num
{
int level, id;
}a[N];
bool cmp1(num x, num y)
{
return x.level < y.level;
}
bool cmp2(num x, num y)
{
return x.id < y.id;
}
bool check(int x, int ed)
{
int l = 1, r = ed, mid;
while (l <= r)
{
mid = (l+r)/2;
if (a[mid].level < x) ans2 = mid, l = mid+1;
else r = mid-1;
}
if (Left - ans2 * x + sum1[ans2] < 0) return 0;
return 1;
}
signed main()
{
cin >> n >> A >> cf >> cm >> m;
for (int i = 1; i <= n; i++) cin >> a[i].level, a[i].id = i;
sort(a+1, a+n+1, cmp1);
ans = -1;
for (int i = 1; i <= n; i++)
{
sum1[i] = sum1[i-1] + a[i].level;
sum2[i] = sum2[i-1] + a[n-i+1].level;
}
for (int i = 0; i <= n; i++)
{
int l = a[1].level, r = A - 1, mid;
Left = m - i * A + sum2[i];
if (Left < 0) break;
if (i == n)
{
if (ans < n * cf + A * cm)
{
ans = n * cf + A * cm;
alevel = A;
aA = n;
}
continue;
}
while (l <= r)
{
mid = (l+r)/2;
if (check(mid, n - i)) ans1 = mid, l = mid + 1;
else r = mid - 1;
}
if (ans < i * cf + ans1 * cm)
{
ans = i * cf + ans1 * cm;
alevel = ans1;
aA = i;
}
}
cout << ans << '\n';
for (int i = 1; i <= aA; i++) a[n-i+1].level = A;
for (int i = 1; i <= n; i++)
{
if (a[i].level >= alevel) break;
a[i].level = alevel;
}
sort(a+1, a+n+1, cmp2);
for (int i = 1; i <= n; i++) cout << a[i].level << " ";
return 0;
}
歡迎關注