这是原本的版本,每次找到新的果汁位置 i 后累加到 tot ,最后用 tot−∑j=0j=k−1j 计算需要移动的次数,但只能得72分。
#include<cstdio>
bool tag[500001]={0};
int main(){
int n,k,a,cnt=0;
long long tot=0;
scanf("%d%d",&n,&k);
if (k>n){
printf("-1");
return 0;
}
for (int i=0;i<n;i++){
scanf("%d",&a);
if (!tag[a]){
tag[a]=1;
tot+=i/*-cnt*/;
cnt++;
if (cnt==k){
printf("%lld\n",tot-k*(k-1)/2);
return 0;
}
}
}
printf("-1");
return 0;
}
不知道哪里出错了,试着更换一下求和顺序,将 tot−∑j=0j=k−1j 中计算位置差的工作,分散到每次识别到新的果汁,也就是 ∑j=0j=k−1jj′−j,结果就可以了:
#include<cstdio>
bool tag[500001]={0};
int main(){
int n,k,a,cnt=0;
long long tot=0;
scanf("%d%d",&n,&k);
if (k>n){
printf("-1");
return 0;
}
for (int i=0;i<n;i++){
scanf("%d",&a);
if (!tag[a]){
tag[a]=1;
tot+=i-cnt;// add "-cnt" here
cnt++;
if (cnt==k){
printf("%lld\n",tot-/*k*(k-1)/2*/);
return 0;
}
}
}
printf("-1");
return 0;
}
在这个数据规模下两种方式应该都不会爆longlong啊,所以是为什么呢?