2 条题解
-
1
本题一看就知道不能直接暴力写,要特殊处理。题目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; }
-
0
#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
- 上传者