A - Sorted Adjacent Differences
1.题意
给定一个整数序列,要求重新排列使它满足|a1−a2|≤|a2−a3|≤…≤|an−1−an|。
2.题解
题目要求构造完成的序列相邻两数的差不递减,我们先把数组排下序,考虑特殊情况(一位大佬说解构造题的窍门是考虑特殊情况~~),差最大的两个数肯定是原序列中的最大值和最小值,所以把它俩放在序列后两位,再把次大值和次小值往前放即可,依此类推。往vector里塞构造后的数组,记得倒序输出。
3.代码
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e5 + 5; int t; int main() { ios::sync_with_stdio(false); cin >> t; while(t--){ int n; int a[maxn] = {0}; cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; } sort(a + 1, a + n + 1); vector<int> ans; for(int i = 1, j = n; i <= j; i++, j--) { if(i == j) { ans.push_back(a[i]); } else { ans.push_back(a[i]); ans.push_back(a[j]); } } for(vector<int>::iterator it = ans.end() - 1; it >= ans.begin(); it--) { if(it == ans.end() - 1) { cout << *it; } else { cout << ' ' << *it; } } cout << endl; } return 0; }
B - Powered Addition
1.题意
给定一个序列,你可以选择其中任意个元素对它们进行k 次操作,操作为让选中的这些元素加上2 ^ (k - 1),最终使序列成为不严格递增序列,要求最小化k 的值。
2.题解
如果一个数大于等于前一个数,那么不动它是最优的,如果小于前一个数,则要给它加上某些数。遍历序列,如果它小于前一个数,就记录下它与前面所有数中最大的数的差,维护序列的最大值和差的最大值,最后填平这个最大差即可。
3.代码
#include<bits/stdc++.h> #define ll long long using namespace std; int t; int main() { ios::sync_with_stdio(false); cin >> t; while(t--) { int n; cin >> n; int a[n + 1] = {0}; for(int i = 1; i <= n; i++) { cin >> a[i]; } //1 7 6 5 int mmax = a[1]; // 7 int cha = 0; // 2 for(int i = 2; i <= n; i++) { mmax = max(mmax, a[i]); if(a[i] < a[i - 1]) { cha = max(cha, mmax - a[i]); } } int ans = 0; while(cha > 0) { cha -= pow(2, ans); ans++; } cout << ans << endl; } return 0; }
C - Middle Class
1.题意
有n 个人,每人有ai 个硬币,若一个人的硬币数不少于x个硬币,则称这个人为富人,求经过任意次操作后富人的最大数量,操作为把m 个人(0 <= m <= n)的硬币平均分给这m 个人。
2.题解
贪心。先按硬币数从大到小排下序,再求一遍前缀和,遍历前缀和,如果sum / i >= x,就说明前i 个人都达到了富人的标准,求出满足条件的最大的i 即可。记得用scanf输入,否则会tle,或者ios::sync_with_stdio(false)来提速。
3.代码
#include<bits/stdc++.h> #define ll long long using namespace std; int t; bool cmp(int x, int y) { return x > y; } int main() { ios::sync_with_stdio(false); cin >> t; while(t--) { ll n, x; ll a[n + 1] = {0}; cin >> n >> x; for(ll i = 1; i <= n; i++) { cin >> a[i]; } sort(a + 1, a + 1 + n, cmp); for(ll i = 1; i <= n; i++) { a[i] += a[i - 1]; } ll ans = 0; for(ll i = 1; i <= n; i++) { if((double)a[i] / (double)i < x) { break; } ans = i; } cout << ans << endl; } return 0; }
D - Circle of Monsters
1.题意
有n 个怪兽围成一个圈,每个怪兽的血量为ai,一次攻击只能对一个怪兽造成一点伤害,当一个怪兽死亡后,会对下一个怪兽造成bi 点伤害,求消灭所有怪兽需要多少次攻击。
2.题解
用爆炸把怪兽打死或打残显然比单纯攻击有效,但是我们要消灭的第一个怪兽必须用攻击而消灭。所以我们用一个数组c 记录怪兽被上个怪兽爆炸后剩下的血量(最少为0),然后求出所有怪兽剩下的血量之和,遍历怪兽,找出最优的起始点(sum - c[i] + a[i]最小)即可。
3.代码
#include<bits/stdc++.h> #define ll long long using namespace std; int t; int main() { ios::sync_with_stdio(false); cin >> t; while(t--) { ll n; cin >> n; ll a[n + 1] = {0}; ll b[n + 1] = {0}; ll c[n + 1] = {0}; for(int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; } c[1] = max((ll)0, a[1] - b[n]); for(int i = 2; i <= n; i++) { c[i] = max((ll)0, a[i] - b[i - 1]); } ll sum = 0; for(int i = 1; i <= n; i++) { sum += c[i]; } ll ans = 9e18; for(int i = 1; i <= n; i++) { ans = min(ans, sum - c[i] + a[i]); } cout << ans << endl; } return 0; }
E - Kind Anton
1.题意
给定两个数组a,b,且数组a 中只包含{-1,0,1} 三个元素中的元素,可任意次操作数组a,问是否能将a变为b。操作为选择一个索引对(i,j),满足i < j,aj 就变为aj + ai。
2.题解
题目要求i 必须小于j ,首先如果两个数组的第一个元素不相等肯定不能成功,直接输出no。如果b 数组中的元素小于a 数组中的对应元素,那么只要在[a1,ai)中存在-1即可,同理, 如果b 数组中的元素大于a 数组中的对应元素,那么只要在[a1,ai)中存在1即可,如果检测到数组a 即出现了-1,也出现了1,那么之后的元素肯定能转变为b数组的元素,直接输出yes结束即可。另外,用一个is记录是否已经输出了no,如果没输出则最后输出yes。
3.代码
#include<bits/stdc++.h> #define ll long long using namespace std; int t; int main() { cin >> t; while(t--) { int n; cin >> n; int a[n + 1] = {0}; int b[n + 1] = {0}; int pos1 = n; int pos2 = n; for(int i = 1; i <= n; i++) { cin >> a[i]; } for(int i = n; i > 0; i--) { if(a[i] == -1) { pos1 = i; } if(a[i] == 1) { pos2 = i; } } for(int i = 1; i <= n; i++) { cin >> b[i]; } int flag1 = 0; int flag2 = 0; int is = 0; if(b[1] != a[1]) { cout << "NO" << endl; } else { for(int i = 2; i <= n; i++) { if(a[i] < b[i]) { if(pos2 < i) { flag2 = 1; } else { cout << "NO" << endl; is = 1; break; } } else if(a[i] > b[i]) { if(pos1 < i) { flag1 = 1; } else { cout << "NO" << endl; is = 1; break; } } if(flag1 && flag2) { break; } } if(!is) { cout << "YES" << endl; } } } return 0; }
1.题意
给定一个序列,如果这个序列的子序列的任意一个子序列和都不为0,则这个子序列合法,要求找出有多少个合法的子序列。
2.题解
我们记fi 表示以i 为结尾的合法段的个数,所以我们要求fi 的和(i 从1到n)。我们考虑依次求出每一个fi ,我们要求的段的右端点显然是i ,左端点可以是[1, i ]中的每一个值,但是哪些左端点是合法的呢?如果左端点是p的时候已经不合法了,那么左端点是q的时候显然也不合法(q < p),因为后者包含了前者所包含的全部子段。那么我们只要求出最小的合法位置p,就知道fi = i - p + 1,i之前可能会有若干个和为0的段,那么p 就是这些段的左端点的最大值+1,所以我们每一次计算完i 的贡献后,要更新左端点的最大值。
计算前缀和ai 后,如果有一个位置j(j < i)满足aj = ai,那么[j + 1, i ]就是一个0段,我们可以用map来存储上一次出现这个数的位置,记作lastpos,那么[lastpos_ai + 1,i ]就是一个0段,p的更新就是max{p ,lastpos_ai + 1},程序里的maxl就是p - 1,所以fi 就是i - maxl,记得开long long。(借鉴大佬的题解)
3.代码
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e5 + 5; ll n, ans; ll a[200005]; map<ll, ll> lastpos; int main() { cin >> n; for(ll i = 1; i <= n; i++){ cin >> a[i]; a[i] += a[i - 1]; } lastpos[0] = 0; for(ll i = 1, maxl = 0; i <= n; i++) { if(lastpos.count(a[i]) != 0) { maxl = max(maxl, lastpos[a[i]] + 1); } ans += i - maxl; lastpos[a[i]] = i; } cout << ans << endl; return 0; }