NC202022. 聚会
描述
输入描述
第一行输入一个正整数表示数据组数，接下来每组数据：
- 第一行输入一个正整数表示聚会邀请的朋友数量。
- 第二行输入个整数，由空格间隔开，第
个整数为
描述第
输入保证。
输出描述
对于每组数据，请输出一个非负整数，表示在最优的摆放传送门的策略下，朋友们最晚需要多长时间可以到达聚会地点。
示例1
输入:
2 2 -2 1 3 4 5 6
输出:
1 1
C++14(g++5.4) 解法, 执行用时: 357ms, 内存消耗: 888K, 提交时间: 2020-04-17 19:15:50
#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100010],n;
bool odk(int x)
{
int l=-2e9,r=2e9;
for(int i=0;i<n;i++)
{
if(abs(a[i])<=x) continue;
l=max(l,a[i]-x);
r=min(r,a[i]+x);
}
return l<=r;
}
void solve()
{
int l=-1,r=1e9,mid;
while(r-l>1)
{
mid=l+r>>1;
if(odk(mid)) r=mid;
else l=mid;
}
printf("%d\n",r);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
solve();
}
}
C++11(clang++ 3.9) 解法, 执行用时: 269ms, 内存消耗: 876K, 提交时间: 2020-04-17 20:19:25
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100005
int a[N];
inline int ab(int x){return x<0?-x:x;}
int main()
{
int T,n,i,ans;
scanf("%d",&T);
while(T--){
scanf("%d",&n);ans=0x3f3f3f3f;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
if(ab(a[1])>ab(a[n]))for(i=1;i<=n;i++)a[i]=-a[i];
sort(a+1,a+n+1);
for(i=1;i<=n;i++)
ans=min(ans,max((a[n]-a[i]+1)>>1,max(ab(a[1]),ab(a[i-1]))));
printf("%d\n",ans);
}
}