题解
1.突然遇到新颖的题,我们可以采用逐步变难法、最简策略法、观察数据法
逐步变难法:
当 \(k=0\) 时, \(ans_0=min(a[i])\)
\(k=1\) 时 \(ans_1=min(ans_0,a[i]-a[i+1](sort))\)
观察数据法:
\(k=2\) 时 观察数据可知 \(n^2\) 左右的算法是可行的,所以我们可以先两端循环遍历所有的第一次 \(|a[i]-a[j]|\) ,再二分查找出最接近的值
易错提醒!!:最小值是数组中的最小值而不是相减后的最小值所以还要有一步 \(ans_2=min(ans_2,ans_1,ans_0)\)
最简策略法:
当 \(k=3\) ,可以前两次得到相同值,第三次得到0,然后无限循环
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[2005]={0};
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n,k;
cin>>n>>k;
for(ll i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1,greater<ll>());
if(k>=3)puts("0");
else if(k==1)
{
ll ans=2e18;
for(ll i=1;i<n;i++) ans=min(ans,a[i]-a[i+1]);
for(ll i=1;i<=n;i++) ans=min(ans,a[i]);
cout<<ans<<endl;
}
else
{
ll ans=2e18;
for(ll i=1;i<n;i++) ans=min(ans,a[i]-a[i+1]);
for(ll i=1;i<=n;i++) ans=min(ans,a[i]);
for(ll i=1;i<=n-1;i++)
{
for(ll j=i+1;j<=n;j++)
{
ll l=1,r=n+1;
ll d1=a[i]-a[j];
while(l+1<r)
{
ll mid=(l+r)/2;
if(a[mid]>=d1) l=mid;
else r=mid;
}
if(l!=n) ans=min(min(abs(d1-a[r]),abs(d1-a[l])),ans);
else ans=min(ans,abs(d1-a[l]));
}
}
cout<<ans<<endl;
}
}
return 0;
}
标签:min,ll,else,Game,abs,ans,Array,d1
From: https://www.cnblogs.com/pure4knowledge/p/18131338