有的人的题解都是差分,我的方法是贪心+模拟,在方法普适性上不及差分,但这题确实可以当做思维题来写.
首先发现前k个中若存在a[i]<a[i+1] (1<=i<=k-1),那我们没有办法使n堆石子数量相等
然后我们可以贪心地从前往后用i遍历每堆石子,观察a[i],a[i+1]的关系,
1.若a[i]<a[i+1],前i堆必须都增加成a[i+1]个石子.
2.若a[i]==a[i+1],那么继续遍历
3.若a[i]>a[i+1],则a[i+1]~a[i+k] 都要增加成a[i]个石子
遍历过程我们始终贪心地立刻使a[i]==a[i+1],
因为你同时增加相邻k堆的数量,若第i堆和第i+1堆同时在这k堆里,那他们的相对关系不变,无法得到a[i]==a[i+1],也就无法使n堆石子数量相等,
只有增加① a[i-k+1]a[i]或② a[i+1]a[i+k],才能改变a[i]和a[i+1]之间的相对关系(显然a[i]小使增加①的数量),所以这个贪心算法的正确性证毕.
下面列出关于贪心过程中判断无法使n堆石子数量相等的条件,证明留给读者
1.a[i]<a[i+1] && i%k!=0 2.a[i]>a[i+1] && i>=n-k+1
最后讲完,发现这个贪心和用差分本质上相同,因为博主知识不扎实故只想出了复杂的较高(因为a[i]>a[i+1]时要模拟改k个值)的贪心模拟法
不过,本方法对理解差分有一定帮助.
代码:
#include<iostream> #include<algorithm> #include<string> #include<string.h> #include<cmath> #define rep(i,a,b) for(ll i=a;i<=b;++i) #define per(i,a,b) for(ll i=a;i>=b;--i) #define fi first #define se second #define mp make_pair #define all(x) x.begin(),x.end() using namespace std; typedef long long ll; const int maxn=1e5+10,inf=0x3f3f3f3f; ll a[maxn]; int main() { int t ; cin>>t; while(t--){ memset(a,0,sizeof(a)); int n,k;cin>>n>>k; rep(i,1,n) cin>>a[i]; ll ans=0; if(k==1){ //特判不是很必要,归并到下面的模拟也行 ll ma=*max_element(a+1,a+1+n); rep(i,1,n){ ans+=ma-a[i]; } cout<<ans<<endl; continue; } bool flag=1; rep(i,1,n-1){ if(a[i]<a[i+1]){ //这里不必模拟修改a[i-k+1]~a[i],因为i向前不回头,我们接下来"认为"前i+1堆都是a[i+1]个石子 if(i%k!=0) {flag=0;break;} else ans+=(a[i+1]-a[i])*(i/k); } else if(a[i]>a[i+1]) { if(i>=n-k+1) {flag=0;break;} else { ll sub=(a[i]-a[i+1]); ans+=sub; rep(j,1,k) a[i+j]+=sub; } } } cout<<(flag?ans:-1)<<endl; } return 0; }