ACM暑期第一次周赛

A题积木大赛

题目大意是有一堆的积木，且所有的积木初始高度都为0，我们每次可以选取一个区间的积木，被选区间的所有的高度都会增加，直到高度与宽度相同，问我们最少操作多少次可以使所有积木达到要求高度。

设d是差分数组

我们要从全 0，通过若干次区间 + 1，得到 h，求最少操作次数。 每次操作只会让一个d正数 + 1、一个d负数 - 1。 所有正数差分的和，就是最少操作次数。

#include <bits/stdc++.h> using namespace std; #define ll long long int main() { int n; cin >> n; vector<int> h(n); for (int i = 0; i < n; ++i) { cin >> h[i]; } ll ans = 0; int pre = 0; for (int x : h) { if (x > pre) { ans += x - pre; } pre = x; } cout << ans << endl; return 0; }

B题前缀

题意给定一个长度为 n 的整数数组，数组元素可正可负。要求找出所有非空连续子数组中和最大的那一段；如果存在多段不同子数组的和同为全局最大值，输出其中长度最小的子数组的长度。 遍历数组时，全程只维护一段以当前遍历元素结尾的连续子数组，每次只做二选一判断： 把当前数字拼到前面这段子数组末尾，得到的总和，如果不如单独只取当前数字大，说明前面一段数字会拉低总和，直接舍弃前面所有内容，重新以当前数字作为新子数组；否则就将当前数字拼接在原有子数组后，区间长度同步加一。每次更新完当前结尾子数组的总和与长度后，和全局记录的最大和做对比：若当前子数组总和 > 全局最大和：更新全局最大和，同时把当前区间长度记为答案； 若当前子数组总和 = 全局最大和：仅当当前区间长度比已存答案更短时，更新答案为更小长度； 若当前子数组总和 < 全局最大和：不做任何操作。

#include<bits/stdc++.h> using namespace std; const int MAXN = 1000010; int a[MAXN]; int main() { int n; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); } long long cur_sum = 0; long long max_sum = -1e18; int cur_len = 0; int ans_len = 0; for(int i = 0; i < n; i++) { if(cur_sum + a[i] < a[i]) { cur_sum = a[i]; cur_len = 1; } else { cur_sum += a[i]; cur_len += 1; } if(cur_sum > max_sum) { max_sum = cur_sum; ans_len = cur_len; } else if(cur_sum == max_sum) { if(cur_len < ans_len) ans_len = cur_len; } } printf("%d", ans_len); return 0; }

D题烦恼的高考志愿

这是一道经典的二分题，思路很简单，我们只需要将学校分数排序之后，通过lower_bound去找第一个大于等于学生分数的位置，然后分别计算差值，记最小的那个差值答案中

#include <bits/stdc++.h> using namespace std; #define ll long long int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, n; cin >> m >> n; vector<int> school(m); for (int i = 0; i < m; ++i) cin >> school[i]; sort(school.begin(), school.end()); ll sum = 0; for (int i = 0; i < n; ++i) { int x; cin >> x; auto it = lower_bound(school.begin(), school.end(), x); int min_d = 1e9; if (it != school.end()) min_d = abs(*it - x); if (it != school.begin()) min_d = min(min_d, abs(*(it - 1) - x)); sum += min_d; } cout << sum << endl; return 0; }

E题跳石头

题意河道起点 0，终点 L，中间 N 块石头，最多搬走 M 块。跳石头时所有跳跃间隔里的最小值，要让这个最小值尽可能大，输出它。二分猜一个间隔mid，要求所有跳跃都不能小于mid。check 函数：从起点 0 往后遍历石头，间距不够 mid 就搬走，统计要搬多少块。搬的数量≤M：mid 可行，尝试更大间隔搬的数量 > M：mid 太大，缩小间隔二分结束，得到能实现的最大最小间隔。

#include <bits/stdc++.h> #define int long long using namespace std; const int N = 50010; int a[N]={0}; int L, n, m; bool check(int mid) { int cnt = 0; int sum = a[0]; for(int i = 1; i <= n + 1; i ++) { int d = a[i] - sum; if(d < mid) cnt ++; else sum = a[i]; } if(cnt <= m) return true; return false; } signed main() { cin >> L >> n >> m; for(int i = 1; i <= n; i ++) cin >> a[i]; a[n + 1] = L; int l = 0, r = L; while(l < r) { int mid = l + r + 1 >> 1; if(check(mid)) l = mid; else r = mid - 1; } cout << l << '\n'; return 0; }