Codeforces Round #835 (Div. 4)A.B.C.D.E.F
A. Medium Number
题目链接：
Problem - A - Codeforces
题面：
题意：
给定三个数，求中间那个数的值
思路：
我们可以分别求出三个数的总和，最大值和最小值，在通过总和减最大值和最小值的方法求出中间的值
代码：
#include<bits/stdc++.h>
using namespace std;
int arr[5];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int maxn = 0;
int minn = 25;
int sum = 0;
for(int i = 0; i < 3; i++){
cin >> arr[i];
maxn = max(maxn, arr[i]);
minn = min(minn, arr[i]);
sum += arr[i];
}
cout << sum - maxn - minn << endl;
}
return 0;
}B. Atilla's Favorite Problem
题目链接：
Problem - B - Codeforces
题面：
题意：
思路：
找到这个字符串里面最大的字符，这个字符的大小就是字母表的大小
代码：
#include<bits/stdc++.h>
using namespace std;
int arr[5];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n ;
string s;
cin >> s;
int maxn = 0;
for(int i = 0; i< n; i++){
maxn = max(maxn, s[i] - 'a' + 1);
}
cout << maxn << endl;
}
return 0;
}C. Advantage
题目链接：
Problem - C - Codeforces
题面：
题意：
给定一个数组，求每个数和除它之外的最大数的差值
思路：
用另一个数组排序这些数字，然后遍历输入数组，如果当前值和最大值不同，就求当前数和最大数的差值，如果相同，就求当前数和第二大数的差值
代码：
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a, int b){
return a > b;
}
int a[200005];
int b[200005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i];
b[i] = a[i];
}
sort(b, b + n, cmp);
for(int i = 0; i < n; i++){
if(i != 0){
cout << " ";
}
if(a[i] != b[0]){
cout << a[i] - b[0];
}else{
cout << a[i] - b[1];
}
}
cout << endl;
}
return 0;
}D. Challenging Valleys
题目链接：
Problem - D - Codeforces
题面：
题意：
给定一个数组，如果只有一个子数组满足条件
就输出yes，否则就输出no
思路：
遍历一遍数组，然后判断有几个子数组满足这个条件即可
代码：
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a, int b){
return a > b;
}
int a[200005];
int b[200005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i];
}
if(n == 1){
cout << "YES" << endl;
continue;
}
int ans = 0;
bool flag = 0;
for(int i = 0; i < n; i++){
if(i == 0){
flag = 1;
}else if(a[i] < a[i - 1]){
flag = 1;
}else if(a[i] > a[i - 1]){
flag = 0;
}
if(i + 1 < n && a[i] < a[i + 1] && flag == 1){
ans++;
flag = 0;
}else if(i + 1 < n && a[i] > a[i + 1]){
flag = 0;
}
}
if(flag){
ans++;
}
if(ans == 1){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
return 0;
}E. Binary Inversions
题目链接：
Problem - E - Codeforces
题面：
题意：
一个01数组，你只能进行一次操作：把一个0变成1或者把一个1变成0，问最多一次操作后数组值最大多少
数组值的计算方法：满足条件的ij对数：i<j&&ai>aj
思路：
对于每个ai为1的i，其后面的0的数量和就是数组值
如果我们把0变成1，那么数组值就会减去前面的1的数量，加上后面的0的数量
把1变成0，减去后面0的数量，加上1的数量
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[200005];
int b[200005];
int c[200005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
b[0] = 0;
c[n + 1] = 0;
for(int i = 1; i <= n; i++){
if(a[i]){
b[i] = b[i - 1] + 1;
}else{
b[i] = b[i - 1];
}
}
ll sum = 0;
ll maxn = 0;
for(int i = n; i >= 1; i--){
if(a[i]){
c[i] = c[i + 1];
sum += c[i];
}else{
c[i] = c[i + 1] + 1;
}
}
maxn = sum;
for(int i = 1; i <= n; i++){
if(a[i]){
maxn = max(maxn, sum - c[i] + b[i] - 1);
}else{
maxn = max(maxn, sum + c[i] - b[i] - 1);
}
}
cout << maxn << endl;
}
return 0;
}F. Quests
题目链接：
Problem - F - Codeforces
题面：
题意：
思路：
如果每天都接最多的任务还是不能道c元，那么就是不可能，如果d天接不同的任务都可以到c元那么k就是任意大，如果都不行，就二分查找k的值
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll arr[200005];
bool cmp(ll a, ll b){
return a > b;
}
bool check(int mid, ll c, int d, int n){
ll sum = arr[0];
for(int i = 1; i <= mid && i < n && i < d; i++){
sum += arr[i];
}
ll ans = d / (mid + 1);
int cnt = d % (mid + 1);
sum *= ans;
for(int i = 0; i < cnt && i < n; i++){
sum += arr[i];
}
if(sum >= c){
return true;
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
ll c;
int d;
cin >> n >> c >> d;
for(int i = 0; i < n; i++){
cin >> arr[i];
}
sort(arr, arr + n, cmp);
ll sum = 0;
for(int i = 0; i < min(n, d); i++){
sum += arr[i];
}
if(sum >= c){
cout << "Infinity" << endl;
}else{
if(arr[0] * d < c){
cout << "Impossible" << endl;
}else{
int l = 0, r = 1e9;
while(l <= r){
int mid = (l + r) / 2;
if(check(mid, c, d, n)){
l = mid + 1;
}else{
r = mid - 1;
}
}
cout << r << endl;
}
}
}
return 0;
}