AKSZ-月赛题4
2024-05-02 17:12:25
发布于:广东
这道题是关于青蛙王国的分配荷叶问题,需要找到合理的分配方式,使得两个部落的青蛙在赏花过程中相邻落脚点的最大距离最小。以下是这道题的解题思路:
- 定义变量和数组来存储输入数据和最小距离。
- 读取输入数据,包括落脚点的数量和坐标,以及初始位置、第一朵荷花和第二朵荷花的坐标。
- 根据初始位置和荷花的坐标,分情况处理:如果初始位置在两朵荷花之间,需要考虑不同的分配情况。
- 计算相邻落脚点的最大距离,并输出最小值。
以上是代码的逻辑,下面解释一下代码各部分的作用:
read
函数:用来快速读入整数。- 主函数中,首先读取输入数据。根据初始位置和荷花的坐标,分情况计算相邻落脚点的最大距离,其中包括初始位置在荷花之间、初始位置在两侧等情况。
- 根据计算得到的最小值,输出相邻落脚点的最大距离。
下面是代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 5;
int n,minn;
int idx,idy1,idy2;
int a[maxn];
inline int read(){
int x = 0, f = 1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main(){
freopen("frogKingdom.in","r",stdin);
freopen("frogKingdom.out","w",stdout);
n = read();minn = 0;
for(int i = 1 ; i <= n;i++) a[i] = read();
idx = read(); idy1 = read(); idy2 = read();
if( (idx > idy1) ^ (idx > idy2)){
if( idy1 > idy2)swap(idy1,idy2);
for(int i = idy1 +1 ; i <= idy2; i++){
minn = max(a[i]-a[i-1],minn);
}
cout << minn << endl;
}else{
if( idx < idy1){
if(idy1 > idy2)swap(idy1,idy2);
for(int i = idy1 + 2 ; i <= idy2; i++){
minn = max(minn,a[i] - a[i-1]);
}
idy2 = idy1 + 1;
int tmp1 = idy1 , tmp2 = idy2;
for(int i = idy1-1; i >= idx ; i--){
if(tmp1 < tmp2){
minn = max(minn,a[tmp2] - a[i]);
tmp2 = i;
}else{
minn = max(minn,a[tmp1] - a[i]);
tmp1 = i;
}
}
}else{
if(idy1 < idy2 ) swap(idy1,idy2);
for(int i = idy2+1 ; i < idy1 ; i ++ ){
minn = max(minn, a[i] - a[i-1]);
}
idy2 = idy1 - 1;
int tmp1 = idy1 , tmp2 = idy2;
for(int i = idy1 + 1; i <= idx; i++){
if(tmp1 > tmp2){
minn = max(minn, a[i] - a[tmp2]);
tmp2 = i;
}else{
minn = max(minn,a[i] - a[tmp1]);
tmp1 = i;
}
}
}
cout << minn << endl;
}
return 0;
}
这里空空如也
有帮助,赞一个