西北工业大学“编程之星”程序设计挑战赛 A 张经理的员工
张经理的员工
https://ac.nowcoder.com/acm/contest/5403/A
解法：
时间复杂度：
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
int a[maxn] , b[maxn];
ll pre[maxn] , fpre[maxn];
ll cpre[maxn] , cfpre[maxn];
int main()
{
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[a[i]]++;
}
ll sum = 0,sum2 = 0;
for(int i=1;i<=100000;i++){
if(b[i]){
sum += 1ll*i*b[i];
sum2 += 1ll*b[i];
}
pre[i] = sum;
cpre[i] = sum2;
}
sum = 0,sum2 = 0;
for(int i=100000;i>=1;i--){
if(b[i]){
sum += 1ll*i*b[i];
sum2 += 1ll*b[i];
}
fpre[i] = sum;
cfpre[i] = sum2;
}
while(q--){
int l,r;
ll ans = 0;
scanf("%d %d",&l,&r);
if(l > r)
swap(l , r);
ll x = 1ll*cpre[l]*l - 1ll*pre[l];
ll y = 1ll*fpre[r] - 1ll*cfpre[r]*r;
ll z = 0 , w = 0;
if(r - l > 1){
int x = r - l;
int l2 = l + x/2;
z = pre[l2] - pre[l] - (cpre[l2] - cpre[l])*l;
int r2 = l2;
w = r*(cpre[r-1] - cpre[r2]) - (pre[r-1] - pre[r2]);
}
cout<<x + y + z + w<<endl;
}
return 0;
}
acm菜鸡日常 文章被收录于专栏
一般写一些打过的比赛题解以及不会的算法
查看8道真题和解析
