4月月赛题解-Dotcpp编程社区

问题A
首先，暴力的做法就是每次挑选两个最小的，然后把这两个最小的数合并，执行m次。
这个复杂度是n^2logn的，我们需要优化。
注意到每次选的数是最小的，这一过程可以用multiset来优化
复杂度O(nlogn)
https://paste.ubuntu.com/p/C44GFpCdFF/
```cpp
// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

multiset <ll> S;
int n, m;

int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++) {
    int x = read();
    S.insert(x);
  }
  while (m--) {
    ll x1 = *S.begin();
    S.erase(S.begin());
    ll x2 = *S.begin();
    S.erase(S.begin());
    S.insert(x1 + x2);
  }
  printf("%lld\n", *S.begin());
}
```
问题B
题目中说 最远的距离最小 ，我们首选二分。
假设距离为x满足条件，那么距离为x+1,x+2,...都满足条件，符合单调性，所以可以二分。
我们贪心考虑，能跳过石子就尽量跳过，最后将跳的次数与m比较即可。
复杂度O(nlogn)
https://paste.ubuntu.com/p/vSQZcvQJ7Q/
```cpp
// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int N = 700005;
int a[N], L, n, m;

bool check(int x) {
  int now = 0, need = 0;
  for (rint i = 1; i <= n; i++) {
    if (a[i] - a[now] > x) {
      now = i - 1;
      need++;
    }
  }
  if (now != n) need++;
  return need <= m;
}
int main() {
  while (~scanf("%d%d%d", &L, &n, &m)) {
    for (rint i = 1; i <= n; i++) a[i] = read();
    sort(a + 1, a + n + 1);
    a[0] = 0, a[++n] = L;
    int l = 0, r = 1e9, ans = 0;
    for (rint i = 1; i <= n; i++) l = max(l, a[i] - a[i - 1]);
    while (l < r) {
      int mid = l + r >> 1;
      if (check(mid)) r = mid;
      else l = mid + 1, ans = mid;
    }
    printf("%d\n", r);
  }
  return 0;
}
```
问题C
显然是一个01背包，但是有点小变形。
我们先将所有的家具排个序，然后从小到大依次塞入背包。
注意细节即可。
复杂度O(nm)
https://paste.ubuntu.com/p/nGkRJNVkqq/
```cpp
// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int N = 20005;

bool f[N];
int a[N], n, m;

int main() {
  while (~scanf("%d", &n) && n) {
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
    }    
    sort(a + 1, a + n + 1);
    scanf("%d", &m);
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (register int i = 1; i <= n; i++) {
      for (register int j = m; j >= 0; j--) {
        if (f[j]) f[j + a[i]] = 1;
      }
    }
    int ans = 0;
    for (int i = N - 1; i >= 0; i--) {
      if (f[i]) {
        ans = i;
        break;
      }
    }
    printf("%d\n", m - ans);
  }
  return 0;
}
```
问题D
这是一个并查集的板子题。
每次x和y相连，那么就将它们合并。最后判断每个团大小的最大值即可。
复杂度O(n)
https://paste.ubuntu.com/p/bwj5ny47mV/
```cpp
// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int N = 10000005;
int f[N], sz[N];
int find(int x) {
  return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int x, int y) {
  x = find(x), y = find(y);
  if (x != y) {
    f[x] = y;
    sz[y] += sz[x];
    sz[x] = 0;
  }
}
int n;
int main() {
  while (~scanf("%d", &n)) {
    for (int i = 1; i <= 10000000; i++) f[i] = i, sz[i] = 1;
    for (int i = 1; i <= n; i++) {
      int x = read(), y = read();
      merge(x, y);
    }
    int ans = 0;
    for (int i = 1; i <= 10000000; i++) if (find(i) == i) {
      ans = max(ans, sz[find(i)]);
    }
    printf("%d\n", ans);
  }
  return 0;
}
```

0.0分

8 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

@独孤求胜

Alan txdy

2020-04-26 00:59:04

刘阿刘

膜拜大佬orz

2020-04-25 22:44:49

陌

orz

2020-04-25 22:40:45

哈尔滨华德学院最菜

Alantxdy

2020-04-25 22:09:38

哈尔滨华德学院最菜

tql

2020-04-25 22:09:19

Kurisu

前排支持alan小姐姐

2020-04-25 22:08:58

«
1
»

等　　级
排　　名	23257
经　　验	592
参赛次数	4
文章发表	1
年　　龄	14
在职情况	学生
学　　校	杭州文澜中学
专　　业	初三学生

Alan

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C++代码）

C二级辅导-同因查找（C语言代码）

简单编码（C++代码）（这里推荐用switch）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

4月月赛题解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

WU-printf基础练习2 （C++代码）

WU-拆分位数（C++代码）

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

演讲大赛评分（C语言代码）

C二级辅导-分段函数（C语言代码）

Alan

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C++代码）

C二级辅导-同因查找 （C语言代码）

简单编码 （C++代码）（这里推荐用switch）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

4月月赛题解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

WU-printf基础练习2 （C++代码）

WU-拆分位数 （C++代码）

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

演讲大赛评分 （C语言代码）

C二级辅导-分段函数 （C语言代码）

C二级辅导-同因查找（C语言代码）

简单编码（C++代码）（这里推荐用switch）

　　评论区

WU-拆分位数（C++代码）

用筛法求之N内的素数。（C语言代码）

演讲大赛评分（C语言代码）

C二级辅导-分段函数（C语言代码）