为什么改变求和顺序就得分不一样?
查看原帖
为什么改变求和顺序就得分不一样?
24347
jiande楼主2024/5/24 12:12

这是原本的版本,每次找到新的果汁位置 ii 后累加到 tottot ,最后用 tot−∑j=0j=k−1jtot-\sum_{j=0}^{j=k-1}j 计算需要移动的次数,但只能得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−1jtot-\sum_{j=0}^{j=k-1}j 中计算位置差的工作,分散到每次识别到新的果汁,也就是 ∑j=0j=k−1jj′−j\sum_{j=0}^{j=k-1}j'_j-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啊,所以是为什么呢?

2024/5/24 12:12
加载中...