战斗 (HG 2018.10.6 T2)

今天的第一题就是暴力模拟。。又是打牌，就不写了 然后T2：  显然，我们不用选多于k的士兵，多了肯定不是最优的。 然后很显然，最小的肯定是连着的。 所以只用O(n)就能枚举出所有要处理的区间，然后因为是类似二次函数型每个区间中二分出最佳答案，取个min就可以了。 下面的程序有点不太对，还是手打二分然后判断在递增还是递减上比较好。 虽然取了平均值附近的很多值，但好像还是会挂。。暴枚了前1000个点才过的 ``` #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define int long long using namespace std; int n,k,ans=1e18; int s1[100100],s2[100100]; int a[100100]; signed main() { // freopen("battle.in","r",stdin); // freopen("battle.out","w",stdout); scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=n;i++) s1[i]=s1[i-1]+a[i]*a[i],s2[i]=s2[i-1]+a[i]; if(n<=1000) { for(int i=k;i<=n;i++) for(int j=i-k+1;j<=i;j++) { int sum=s2[i]-s2[i-k]; ans=min(ans,(s1[i]-s1[i-k])-2*sum*a[j]+k*a[j]*a[j]); } } else { for(int i=k;i<=n;i++) { int sum=s2[i]-s2[i-k],avr=sum/k; int p=lower_bound(a+(i-k)+1,a+i+1,avr)-a-1; int q=lower_bound(a+(i-k)+1,a+i+1,avr)-a-1; ans=min(ans,(s1[i]-s1[i-k])-2*sum*a[p]+k*a[p]*a[p]); if(p+1<=i) ans=min(ans,(s1[i]-s1[i-k])-2*sum*a[p+1]+k*a[p+1]*a[p+1]); if(p-1>=i-k+1) ans=min(ans,(s1[i]-s1[i-k])-2*sum*a[p-1]+k*a[p-1]*a[p-1]); if(p+1<i) ans=min(ans,(s1[i]-s1[i-k])-2*sum*a[p+2]+k*a[p+2]*a[p+2]); if(p-1>i-k+1) ans=min(ans,(s1[i]-s1[i-k])-2*sum*a[p-2]+k*a[p-2]*a[p-2]); ans=min(ans,(s1[i]-s1[i-k])-2*sum*a[q]+k*a[q]*a[q]); if(q+1<=i) ans=min(ans,(s1[i]-s1[i-k])-2*sum*a[q+1]+k*a[q+1]*a[q+1]); if(q-1>=i-k+1) ans=min(ans,(s1[i]-s1[i-k])-2*sum*a[q-1]+k*a[q-1]*a[q-1]); if(q+1<i) ans=min(ans,(s1[i]-s1[i-k])-2*sum*a[q+2]+k*a[q+2]*a[q+2]); if(q-1>i-k+1) ans=min(ans,(s1[i]-s1[i-k])-2*sum*a[q-2]+k*a[q-2]*a[q-2]); } } printf("%lld",ans); return 0; } ```