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; vectorint 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 的整数数组数组元素可正可负。要求找出所有非空连续子数组中和最大的那一段如果存在多段不同子数组的和同为全局最大值输出其中长度最小的子数组的长度。 遍历数组时全程只维护一段以当前遍历元素结尾的连续子数组每次只做二选一判断 把当前数字拼到前面这段子数组末尾得到的总和如果不如单独只取当前数字大说明前面一段数字会拉低总和直接舍弃前面所有内容重新以当前数字作为新子数组否则就将当前数字拼接在原有子数组后区间长度同步加一。每次更新完当前结尾子数组的总和与长度后和全局记录的最大和做对比若当前子数组总和 全局最大和更新全局最大和同时把当前区间长度记为答案 若当前子数组总和 全局最大和仅当当前区间长度比已存答案更短时更新答案为更小长度 若当前子数组总和 全局最大和不做任何操作。#includebits/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; vectorint 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 就搬走统计要搬多少块。搬的数量≤Mmid 可行尝试更大间隔搬的数量 Mmid 太大缩小间隔二分结束得到能实现的最大最小间隔。#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; }