0

我正在编写一段代码，我必须执行除以 2。以下代码行给出了正确的输出

ans = ans + ((long long)cnt * (cnt-1))/2;

但是，当我将其更改为

ans = ans + ((long long)cnt * (cnt-1)) >> 1;

上面的代码有什么问题

在我的设置中，这些值永远不会是负数

这是代码

#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
int s[1000000];
int main(){_
int t;
cin>>t;
while(t--){
    int n,i,z,sum=0,p,cnt=0;
    unsigned long long int ans=0;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>z;
        sum+=z;
        s[i]=sum;
    }
    sort(s,s+n);
    i=0;
    while(i<n){
        p=s[i];
        cnt=0;
        while(s[i]==p){
            cnt++;
            i++;
        }
        ans=ans+((unsigned long long)cnt*(cnt-1))>>1;
    }
    cnt=0;
    for(int i=0;i<n && s[i]<=0;i++){
        if(s[i]==0){
            cnt++;
        }
    }
    ans+=cnt;
    cout<<ans<<"\n";
}
return 0;
}

对于输入 1 4 0 1 -1 0

输出是 4 但它应该是 6

此外，该代码为高输入提供 Sigsegv 错误

1<=t<=5

1<=n<=10^6

-10<= z <= 10

4

2 回答 2

6

运算符>>的优先级低于+（当然还有/），因此您编写了相当于：

ans = ( ans + ((long long)cnt * (cnt-1)) ) >> 1;
//    ^--- note these -------------------^
于 2013-11-04T18:35:24.297 回答
1

对于 sigsegv 问题，我猜这是在此处的内部循环中的某些条件下，i索引运行超过数组末尾的结果：s[]

while(i<n){
       p=s[i];
       cnt=0;
       while(s[i]==p){
           cnt++;
           i++;         // <== I'm not convinced this will always remain less than n
                        //     or less than 1000000 depending on the data set and 
                        //     what happens to be in memory after `s[]`
       }
       ans=ans+((unsigned long long)cnt*(cnt-1))>>1;
}
于 2013-11-04T19:04:56.137 回答