¶ D1 ( )
链接:https://codeforces.com/contest/1706/problem/D1
滑动窗口,每个
代码:
#include <cstdio>
#include <queue>
using namespace std;
constexpr int MAXN = 3011;
int main() {
int T;
static int a[MAXN];
static int p[MAXN];
"%d", &T);
scanf(while (T--) {
int n, k;
"%d%d", &n, &k);
scanf(for (int i = 1; i <= n; ++i) {
"%d", a + i);
scanf(
}int ans = 0x3f3f3f3f;
int mn = 0x3f3f3f3f;
int, int> > pq;
priority_queue<pair<for (int i = 1; i <= n; ++i) {
1;
p[i] =
}for (int i = 1; i <= n; ++i) {
pq.push(make_pair(a[i], i));
mn = min(mn, a[i]);
}while (1) {
int mx = pq.top().first;
int i = pq.top().second;
pq.pop();
ans = min(ans, mx - mn);if (p[i] == k) {
break;
}1;
p[i] += int v = a[i] / p[i];
pq.push(make_pair(v, i));
mn = min(mn, v);
}"%d\n", ans);
printf(
}
return 0;
}
¶ D1 ( )
注意到
代码:
#include <cstdio>
#include <queue>
using namespace std;
constexpr int MAXN = 3011;
int main() {
int T;
static int a[MAXN];
static int p[MAXN];
"%d", &T);
scanf(while (T--) {
int n, k;
"%d%d", &n, &k);
scanf(for (int i = 1; i <= n; ++i) {
"%d", a + i);
scanf(
}int ans = 0x3f3f3f3f;
int mn = 0x3f3f3f3f;
int, int> > pq;
priority_queue<pair<for (int i = 1; i <= n; ++i) {
1;
p[i] =
}for (int i = 1; i <= n; ++i) {
pq.push(make_pair(a[i], i));
mn = min(mn, a[i]);
}while (!pq.empty()) {
int mx = pq.top().first;
int i = pq.top().second;
pq.pop();
ans = min(ans, mx - mn);if (mx == 0)
break;
1;
p[i] = a[i] / mx + if (p[i] > k)
break;
int v = a[i] / p[i];
pq.push(make_pair(v, i));
mn = min(mn, v);
}"%d\n", ans);
printf(
}
return 0;
}
¶ D2 ( )
D2的n和
注意到值域仅为1e5,因此可以采用类似桶排序的思路,搞一个数组
代码:
#include <cstdio>
#include <vector>
using namespace std;
constexpr int MAXN = 100011;
constexpr int MAXV = 100011;
int main() {
int T;
static int a[MAXN];
static int p[MAXN];
"%d", &T);
scanf(while (T--) {
int n, k;
"%d%d", &n, &k);
scanf(for (int i = 1; i <= n; ++i) {
"%d", a + i);
scanf(
}int ans = 0x3f3f3f3f;
int mn = 0x3f3f3f3f;
int> v[MAXV];
vector<for (int i = 1; i <= n; ++i) {
1;
p[i] =
}int mx = a[1];
for (int i = 1; i <= n; ++i) {
v[a[i]].push_back(i);
mn = min(mn, a[i]);
mx = max(mx, a[i]);
}for (; mx; mx -= 1) {
if (v[mx].empty())
continue;
for (int i : v[mx]) {
ans = min(ans, mx - mn);1;
p[i] = a[i] / mx + if (p[i] > k)
goto out;
int val = a[i] / p[i];
v[val].push_back(i);
mn = min(mn, val);
}int>();
v[mx] = vector<
}
out:"%d\n", ans);
printf(
}
return 0;
}
¶ D2 ( )
假设已知
要最大化
换句话说,假如
这里官方题解
这样,我们遍历
但是怎么求出这个最小值呢?注意到对每个
总的算法流程是枚举最大值
注意到
由于
遍历
因此总的复杂度为
代码:
#include <cstdio>
#include <vector>
using namespace std;
constexpr int MAXN = 100011;
constexpr int MAXV = 100011;
int main() {
int T;
static int a[MAXN];
static int ge[MAXV];
"%d", &T);
scanf(while (T--) {
int n, k;
"%d%d", &n, &k);
scanf(0] = 0;
a[for (int i = 1; i <= n; ++i) {
"%d", a + i);
scanf(
}for (int i = n; i; --i) {
for (int j = a[i]; j > a[i-1]; --j) {
ge[j] = a[i];
}
}0] = a[1];
ge[int ans = 0x3f3f3f3f;
for (int v = a[n] / k; v <= a[n]; ++v) {
int mn = 0x3f3f3f3f;
for (int u = 1; u <= a[n] / (v + 1) + 1; ++u) {
int ai = ge[(u - 1) * (v + 1)];
if (ai < u * (v + 1)) {
mn = min(mn, ai / u);
}
}
ans = min(ans, v - mn);
}"%d\n", ans);
printf(
}
return 0;
}