题目来源：https://codeforces.com/gym/105161
文章目录
写在前面：今天打的训练赛打的很水·····，我发现我们队做二分的问题做的太少了，即使看的出是二分，一样也是写不出check函数，可能是以前只做过简单的二分答案，遇到稍微难一些的二分就写不出来了，赛后得多刷刷二分答案的问题。
回归正题
F - Download Speed Monitor
题意
从第k秒开始显示下载速率，若下载速率大于等于1024，则需要进行转化。
思路
签到题，用数组模拟栈即可，后一个数进来前一个数出去。
编程
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N=1e5+5;
int a[N];
void solve(){
int n,k;
cin >> n >> k;
double sum=0;
for(int i=1;i<=n;++i){
cin >> a[i];
if(i<=k-1){
sum+=a[i];
}
else{
sum+=a[i];
if((sum/k)>=1024){
printf("%.6f MiBps\n",1.0*sum/k/1024);
}
else printf("%.6f KiBps\n",1.0*sum/k);
sum-=a[i-k+1];
}
}
return ;
}
signed main(){
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
//cin >> t;
while(t--) solve();
// cout << fixed;//强制以小数形式显示
// cout << setprecision(n); //保留n位小数
return 0;
}
G - Download Time Monitor
题意
给你网络宽带每秒下载速度的大小，以及两个文件的内存和开始时间，判断这两个文件需要多久才能下完（需要考虑时间重复的情况）
思路
也是一个签到题，比F题稍微复杂一点，需要考虑三种情况：
- 两个文件下载的时间互不影响
- 两个文件开始的时间相同
- 两个文件下载的时间有重叠部分
考虑以上情况即可写出这道题
编程
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N=1e6+5;
int a[N];
void solve(){
double b,t1,a1,t2,a2;
scanf("%lf%lf%lf%lf%lf",&b,&t1,&a1,&t2,&a2);
int t=t2-t1;//时间差
if(t==0){//开始时间相同
b=b/2;
double ans1=0,ans2=0;
if(a1>=a2){//有重叠部分
ans2=a2/b;
ans1=ans2;
b*=2;
ans1+=(a1-a2)/b;
printf("%.9f ",ans1);
printf("%.9f\n",ans2);
return ;
}
else{
ans1=a1/b;
ans2+=ans1;
b*=2;
ans2+=(a2-a1)/b;
printf("%.9f ",ans1);
printf("%.9f\n",ans2);
return ;
}
}
else{
if(a1/b<=t)//时间互不影响
{
printf("%.9f ",a1/b);
printf("%.9f\n",a2/b);
return ;
}
else{//有重叠部分
double ans1=0,ans2=0;
a1-=t*b;
ans1+=t;
b/=2;
if(a1>=a2){
ans2+=a2/b;
ans1+=a2/b;
b*=2;
ans1+=(a1-a2)/b;
printf("%.9f ",ans1);
printf("%.9f\n",ans2);
return ;
}
else{
ans1+=a1/b;
ans2+=a1/b;
b*=2;
ans2+=(a2-a1)/b;
printf("%.9f ",ans1);
printf("%.9f\n",ans2);
return ;
}
}
}
return ;
}
signed main(){
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
scanf("%d",&t);
while(t--) solve();
// cout << fixed;//Ç¿ÖÆÒÔСÊýÐÎʽÏÔʾ
// cout << setprecision(n); //±£ÁônλСÊý
return 0;
}
K - Number Deletion Game
题意
两个人进行博弈操作，每个人可以删去一个最大的数x，然后选择任意小于x的数字y，新增1，2，···y各一个，特别的当y=0，不加任何数字，谁删去最后一个数谁就获胜
思路
找规律，通过枚举可以发现：当最大的数字为奇数时，Alice必赢，反之为偶数时，Alice必输。因为最大的数字可以影响比它小的所有数，只要保证Alice开始时有着奇数个最大的数，那么他执行一步后可以将次最大的数变为偶数，只要有人执行的最大的数为偶数时，他必输，你们可以自己举例试试，本文不举例子，所以只要判断最大数的奇偶性即可。
编程
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N=1e3+5;
void solve(){
int n;cin >> n;
int sum=0;
int cnt=0;
for(int i=1;i<=n;++i){
int x;cin >> x;
if(x==cnt) sum++;
else if(x>cnt){
sum=1;
cnt=x;
}
}
if(sum%2) cout << "Alice" << endl;
else cout << "Bob" << endl;
return ;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
//cin >> t;
while(t--) solve();
// cout << fixed;//Ç¿ÖÆÒÔСÊýÐÎʽÏÔʾ
// cout << setprecision(n); //±£ÁônλСÊý
return 0;
}
I - Integer Reaction
题意
有一串n序列的 a i a_i ai,这些整数有0和1的颜色，当序列为0的数字遇到序列为1时，必须进行消除操作（将这两个数x和y进行相加操作），然后存入一个S集合里面，若x索引不到y，则不进行消除操作，判断S集合里面最小元素的最大值是多少
思路
求最小···的最大值即可判断这题用二分，那么此题的难点在于check函数如何写，我们可以用multiset建立两个集合，一个用来存放1颜色的数字，一个用来存入0颜色的数字，由于此题单纯遍历两个集合会超时，我们可以考虑用lower_bound来二分集合里面的元素，由x+y=mid,我们可以推出y=mid-x，因此我们只需要查找另一个集合是否有大于等于mid-x的数，若有则删去该数，若没有则直接return false，循环结束说明mid满足，则return true，外边套用二分求右边界即可。
编程
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N=1e5+5;
int a[N],b[N];
int n;
bool check(int x){
multiset<int> s1,s2;
for(int i=1;i<=n;++i){
if(b[i]==0){
if(s1.empty()) s2.insert(a[i]);//若1集合里面为空，那么就存入0集合里
else{
auto t=s1.lower_bound(x-a[i]);//集合里面二分找比mid-a[i]大的数
if(t==s1.end()) return false;//找不到直接return
else s1.erase(t);//找到则删除该数
}
}
else{
if(s2.empty()) s1.insert(a[i]);
else{
auto t=s2.lower_bound(x-a[i]);
if(t==s2.end()) return false;
else s2.erase(t);
}
}
}
return true;//循环完全结束则mid满足题意
}
void solve(){
cin >> n;
int maxn=0;
for(int i=1;i<=n;++i){
cin >> a[i];
maxn=max(maxn,a[i]);
}
for(int i=1;i<=n;++i) cin >> b[i];
int l=0,r=2*maxn+1;
while(l<r){//二分求右边界
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout << l << endl;
return ;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
//cin >> t;
while(t--) solve();
// cout << fixed;//强制以小数形式显示
// cout << setprecision(n); //保留n位小数
return 0;
}