2 条题解

  • 1
    @ 2022-11-6 14:26:02

    本题一看就知道不能直接暴力写,要特殊处理。题目ai的范围是0~1000,看到这里就知道只需要拿一个桶记录0到1000里面的每个数出现了几次,比如序列a里面有n个100,m个300, 则公式的答案就是nxmx|100+300-1000|, 如果n个100, 则答案是nx(n+1)x|100+100-1000| 所以只需要遍历0到1000,求出每个数能得到的答案的和即可 代码如下

    #include<bits/stdc++.h>
    #define ll long long
    const int N=1e6+9; 
    using namespace std;
    ll v[N];
    int main()
    {
    	int n,x;
    	cin >> n;
    	for( int i = 1; i <= n; i++)
    	{
    		cin >> x;
    		v[x]++;
    	}
    	ll sum=0,y;
    	for( int i = 0; i <= 1000; i++)
    	{
    		for( int j = i; j <= 1000; j++)
    		{
    			if(i==j) y=v[i]+v[i]*(v[j]-1)/2;
    			else y= v[i]*v[j];
    			sum+=y*abs(i+j-1000);
    		}
    	}
    	cout << sum << endl;
    	return 0;
    }
    
    • @ 2022-11-7 19:29:50

      i==j的时候,改成等差数列前n项和多好理解

  • 0
    @ 2022-11-6 21:33:09
    #include<iostream>
    #include<algorithm>
    #include<string.h>
    #include<queue>
    using namespace std;
    const int maxn=1e6+10;
    long long a[maxn],sum[maxn];
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++){
    		scanf("%lld",&a[i]);
    	}
    	sort(a+1,a+1+n);
    	for(int i=1;i<=n;i++){
    		sum[i]=sum[i-1]+a[i];
    	}
    	long long ans=0;
    	for(int i=1;i<=n;i++){
    		long long l=i,r=n+1;
    		while(l<r){
    			long long mid=(l+r)/2;
    			if(a[mid]<1000-a[i]){
    				l=mid+1;
    			}else{
    				r=mid;
    			}
    		}·
            ans=ans+(1000-a[i])*(r-i);
            ans=ans-(sum[r-1]-sum[i-1]);//处理负数的部分
            ans=ans+a[i]*(n-r+1)+(sum[n]-sum[r-1]);
            ans=ans-1000*(n-r+1);//处理正数的部分
    	}
    	printf("%lld",ans);
    	return 0;
    }
    

    二分加前缀和的傻子解法(0^0)

    • 1

    信息

    ID
    832
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    141
    已通过
    11
    上传者