数学（九） (5-2)

std::cin＞＞b＞＞k;

auto check = [&](int dis)

{

int p1 = std::lower_bound(a.begin(), a.end(), b - dis) - a.begin();

int p2 = std::upper_bound(a.begin(), a.end(), b + dis) - a.begin() - 1;

return p2 - p1 + 1＜k;

};

int l = -1, r = 2e8;

while (l＜r)

{

int mid = (l + r + 1) / 2;

if (check(mid))

l = mid;

else

r = mid - 1;

}

std::cout＜＜l + 1＜＜"\n";

}

return 0;

}

E - Maximum Glutton

到E 直接开始破防，确实是 dp 功力还不行

枚举前面i 个里面选 j 个，甜度不超过 k 的最小代价，然后可以把第一维滚掉

int main()

{

std::ios::sync_with_stdio(false);

std::cin.tie(0);

int n;

std::cin＞＞n;

int x, y;

std::cin＞＞x＞＞y;

std::vector＜int＞ a(n + 1), b(n + 1);

for (int i = 1; i ＜= n; i++)

{

std::cin＞＞a[i]＞＞b[i];

}

std::vector dp(n + 1, std::vector＜int＞(x + 1, y + 1));

dp[0][0] = 0;

for (int i = 1; i ＜= n; i++)

{

auto ndp = dp;

for (int j = 1; j ＜= i; j++)

{

for (int k = a[i]; k ＜= x; k++)

{

ndp[j][k] = std::min(ndp[j][k], dp[j - 1][k - a[i]] + b[i]);

}

}

dp.swap(ndp);

}

int ans = 0;

for (int j = 0; j＜n; j++)

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。