原题地址：Codeforces Round #835 (Div. 4)
题目：A. Medium Number
题意：
没什么好说的，输出中间那个数即可
代码：
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<string.h>
typedef long long ll;
using namespace std;
const int N = 1e5+10;
const int mod = 1e9+7;
ll a[N],b[N],c[N];
//string s1[N],s2[N],s3[N];
int main(void)
{int t;cin >> t;while(t--){for(int i=1;i<=3;i++){cin >> a[i];} sort(a+1,a+4);cout << a[2] << endl;}return 0;} 题目：B. Atilla's Favorite Problem
题意：
给定一个字符串s，输出ASCII码最大的字符对应的数字即可
代码：
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<string.h>
typedef long long ll;
using namespace std;
const int N = 1e5+10;
const int mod = 1e9+7;
ll a[N],b[N],c[N];
//string s1[N],s2[N],s3[N];
int main(void)
{int t;cin >> t;while(t--){int n;cin >> n;string s;cin >> s;int ma=0;for(int i=0;i<n;i++){int num = s[i]-'a'+1;ma = max(ma,num);}cout << ma << endl;}return 0;} 题目：C. Advantage
题意：
给定一个长度为n的数组a[],求每一个元素跟其他元素最大值的差值，这题的思路就是：如果此时元素是数组中最大的，则输出它与整个数组第二大的差值，否则，输出与最大元素的差值即可，即是需要找到数组中第一和第二大的值的下标即可
代码：
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<string.h>
typedef long long ll;
using namespace std;
const int N = 2e5+10;
const int mod = 1e9+7;
ll a[N],b[N],c[N];
//string s1[N],s2[N],s3[N];
//struct my{
// ll num;
// int id;
//};
//my mys[N];
//bool mysort(my m1,my m2)
//{
// return m1.num<m2.num;
//}
int main(void)
{int t;cin >> t;while(t--){int n;cin >> n;map<int,int> m;ll ma1=0;int index=0;for(int i=1;i<=n;i++){cin >> a[i];if(a[i]>ma1){index = i;ma1 = a[i];}}ll ma2 = 0;for(int i=1;i<=n;i++){if(i!=index){ma2 = max(ma2,a[i]);}}for(int i=1;i<=n;i++){if(i!=index){cout << a[i]-ma1 << " ";}else{cout << a[i]-ma2 << " ";}}cout << endl;}return 0;} 题目：D. Challenging Valleys
题意：
给定一个长度为n的数组a[],如果数组满足有且仅有一个valley,则输出yes，否则输出no
比如样例
8
9 4 4 5 9 4 9 10
可以看出, 4 4 夹在 9 和 5中间，且左边4比9小，右边4比5小，所以满足valley，而右边的4,左边是9，右边也是9，同样满足valley,所以有俩个满足valley的，输出no
直接代码模拟一编过程就可以了
代码：
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<string.h>
typedef long long ll;
using namespace std;
const int N = 2e5+10;
const int mod = 1e9+7;
ll a[N],b[N],c[N];
//string s1[N],s2[N],s3[N];
//struct my{
// ll num;
// int id;
//};
//my mys[N];
//bool mysort(my m1,my m2)
//{
// return m1.num<m2.num;
//}
int main(void)
{int t;cin >> t;while(t--){int n;cin >> n;int aa=1;for(int i=1;i<=n;i++){cin >> a[i];}int cnt=0;int l=1,r=1;//刚开始l和r相等，因为valley也可以是单个值a[0] = 1e9+10;//保证左边界成立a[n+1] = 1e9+10;//保证有边界成立for(int i=1;i<=n;i++){//如果满足l小于左边，r小于右边，则是valley，cnt++即可if(a[l]<a[l-1]&&a[r]<a[r+1]){l = r+1;r = l;cnt++;continue;}//如果r跟r+1相等,则证明它们是相同元素，所以r++if(a[r]==a[r+1]){r++;continue;}//继续找l = r+1;r = l;}if(cnt==1)cout << "YES" << endl;elsecout << "NO" << endl; }return 0;} 题目：E. Binary Inversions
题意：
给定一个长度为n的数组a[],里面元素的值只包含1和0，可以选择进行一次操作（将数组a里的一个1变成0，或者0变成1，但是只能改一个），也可以选择不操作。求最后组成 “1 0”的组合最多
1要在前面，0要在后面
这道题的思路就是：如果我要选择将1变成0，那么我肯定选择把最后面的那个1改为0划算
比如 1 0 1 0 1，如果我们改变第三个1为0，那么个数是(1,2),(1,3),(1,4)三个(注意括号里的是下标位置)，如果我们改变第五个1为0,则有(1,2),(1,5),(1,4),(3,4) (3,5) 五个，所以改后面的0为1是最多的.
同理如果要选择将0变为1,则肯定把最前面的0改为1划算
最后一种是不进行操作，如 1 1 0 0 ，不进行操作是最多的
所以我们把这三种情况依次比较一下即可，找到最大的那个选法
代码：
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<string.h>
typedef long long ll;
using namespace std;
const int N = 2e5+10;
const int mod = 1e9+7;
ll a[N],b[N],c[N];
//string s1[N],s2[N],s3[N];
//struct my{
// ll num;
// int id;
//};
//my mys[N];
//bool mysort(my m1,my m2)
//{
// return m1.num<m2.num;
//}
int main(void)
{int t;cin >> t;while(t--){int n;cin >> n;for(int i=1;i<=n;i++){cin >> a[i];b[i] = a[i];c[i] = a[i];}ll res=0;for(int i=1;i<=n;i++){if(a[i]==0){a[i] = 1;break;}}ll sum1=0,c1=0;for(int i=1;i<=n;i++){if(a[i]){c1++;}else{sum1 += c1;}}res = max(res,sum1);for(int i=n;i>=1;i--){if(b[i]){//cout << i << endl;b[i] = 0;break;}}sum1=0,c1=0;for(int i=1;i<=n;i++){//cout << b[i] << " ";if(b[i]){c1++;}else{sum1 += c1;}}res = max(sum1,res);sum1=0;c1 = 0;for(int i=1;i<=n;i++){//cout << b[i] << " ";if(c[i]){c1++;}else{sum1 += c1;}}res = max(sum1,res);cout << res << endl;}return 0;}
题目：F. Quests
题意：
给定一个长度为n的数组a[],和一个c，一个d.每天可以选择一个quest回答并得到对应的分值，这时候定义一个k，当你回答一个quest时，在接下来的k天，你都不能选择这个quest回答，求问，能否找到一个最大的k，使得在d天内获取的分值>c
思路:
分为三种情况
第一种"Impossible": 当k=0时，我们每天都可以选择相同的quest进行回答，那么肯定会选择分值最大的那个quest，所以在d天内获得的分值为sum = d*a[max],如果sum<c的话，则证明无论如何，k都不能满足
第二种“Infinity”:
当d>n时，无论k取得有多大，每一个quest至少可以回答一次，所以此时最小得sum = 数组a所有元素的和,如果sum > c，则证明k取任何值都能满足
当d<=n时，有些元素可能取不到，但是我们优先从大到小可以取d个元素,所以sum = d个元素的和，如果sum > c，则证明k取任何值都能满足
第三种：肯定能找出那个k
所以我们使用二分法来找到那个k，k一定是从0到d中的莫一个，所以用二分法不断找到那个k,设置一个left和一个right，此时的k = mid = (left+right+1)/2，加一是为了防止边界问题，用此时的k去模拟得到sum，如果sum<c,则证明k取大了，将right缩小，否则，则k取小了，将left增大，直到最后left = right为止，此时的left = right = k就是我们要找的最大的k
代码：
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<string.h>
typedef long long ll;
using namespace std;
const int N = 2e5+10;
const int mod = 1e9+7;
ll a[N],b[N],c[N];
//string s1[N],s2[N],s3[N];
//struct my{
// ll num;
// int id;
//};
//my mys[N];
//bool mysort(my m1,my m2)
//{
// return m1.num<m2.num;
//}
int main(void)
{int t;cin >> t;while(t--){ll n,c,d;cin >> n >> c >> d;for(int i=1;i<=n;i++){cin >> a[i];}sort(a+1,a+n+1);if(a[n]*d<c){cout << "Impossible" << endl;continue;} ll mi = min(n,d);ll index=n;ll sum=0;while(mi--){sum+=a[index];index--;}if(sum>=c){cout << "Infinity" << endl;continue;}ll left = 0,right = d+1;//right取大一点，防止边界问题 while(left!=right){memset(b,0,sizeof b);ll coins = 0;ll mid = (left+right+1)/2;ll day=1;for(int i=n;i>=1&&day<=d;i--){//b[day]的意思是，如果当前的天数已经被使用过了，则直接continue即可if(b[day]){continue;}ll cday = day;while(cday<=d){coins+=a[i];//标记这天已经被使用过了b[cday] =1;cday+=mid+1;}day++;} //cout << mid << " " << coins << endl;if(coins<c){right = mid-1;}else{left = mid;}}cout << left << endl;}return 0;} 谢谢观看！
