Codeforces Round 931 (Div. 2)

本文主要是介绍Codeforces Round 931 (Div. 2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. Too Min Too Max

将绝对值去掉，发现最大的情况是两个最大的值减去两个最小的值，再乘2

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=110;
int a[N];
int n;
void solve() {cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);int ans=(a[n]+a[n-1]-a[1]-a[2])*2;cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

B. Yet Another Coin Problem

参考Codeforces Round 931 (Div. 2) (A~B)-CSDN博客

这题一开始觉得贪心不可取

但实际上在大于某个阈值时贪心选择15一定是正确合理的，设想当数很大很大时，肯定用最大的15

阙值大概在30，因为30是1，3，6，10，15的最小公倍数

30以内的用完全背包，选择n / 15 - 1个15面额的硬币，剩余钱数n%15+15 dp即可

trick：
这题一开始想用贪心，发现不可行，又想用完全背包，又不可行，那么将两者结合，阙值以上贪心，，阙值以下完全背包

#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;
const int N=110;
int f[N];
int v[5]={1,3,6,10,15};
int n;
void solve() {cin>>n;if(n<=30) cout<<f[n]<<endl;else cout<<n/15-1+f[n%15+15]<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);memset(f,0x3f,sizeof f);f[0]=0;for(int i=0;i<5;i++){for(int j=v[i];j<=30;j++){f[j]=min(f[j],f[j-v[i]]+1);}}int t=1;cin>>t;while(t--) {solve();}return 0;
}

C. Find a Mine

交互题
最多问4次
问（x，y）
可以得到两个地雷离（x，y）最近的曼哈顿距离
目标确定其中一个地雷的位置

第一次问（1，1）
得到x，说明其中一个地雷在第x+1条对角线上（左下右上方向）
然后通过问对角线的右上角，然后得到对角线上的那个地雷的可能位置，但是有可能受第二个地雷干扰，所以是可能位置，可能第二个地雷离它更近

通过问对角线的左下角，得到对角线上的那个地雷的可能位置，如果通过右上角得到的是假位置，那么通过左下角得到的一定是真位置，因为如果第二个地雷距右上角比第一个地雷距右上角近的话，那么第一个地雷距左下角绝对比第二个地雷距左下角近

综上，问（1，1），问得到的对角线的左上角和右下角，以此确定出的两个可能位置，两个位置中一定有一个是对的，所以只要问其中一个位置就行，最多问4次

坑点：

交互题，每个输出语句下都要有cout.flush();

之前return的时候一般不写也能过，这次就过不了了

以后每个输出语句下都要写

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,m;
void solve() {cin>>n>>m;cout<<"? "<<1<<' '<<1<<endl;cout.flush();int x;cin>>x;if(x==0){cout<<"! "<<1<<' '<<1<<endl;cout.flush();return;}int duijiao=x+1;//在第x+1条对角线 int a,b;if(duijiao<=m) a=1,b=duijiao;else{b=m;a=1+duijiao-m;}cout<<"? "<<a<<' '<<b<<endl;cout.flush();cin>>x;if(x==0){cout<<"! "<<a<<' '<<b<<endl;cout.flush();return;}x/=2;a+=x,b-=x;cout<<"? "<<a<<' '<<b<<endl;cout.flush();cin>>x;if(x==0){cout<<"! "<<a<<' '<<b<<endl;cout.flush();return;}if(duijiao<=n){a=duijiao;b=1;}else{a=n;b=1+duijiao-n;}cout<<"? "<<a<<' '<<b<<endl;cout.flush();cin>>x;if(x==0){cout<<"! "<<a<<' '<<b<<endl;cout.flush();return;}x/=2;a-=x,b+=x;cout<<"! "<<a<<' '<<b<<endl;cout.flush();
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}