首页 > 代码库 > ACDream - Sum

ACDream - Sum

2024-07-15 06:04:45   228人阅读

先上题目：

Sum

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
SubmitStatus

Problem Description

给出N,a[1]... a[N]，还有M,b[1]... b[M]
long long ans = 0;
for(int i = 1; i <= N; i ++)
    for(int j = 1; j <= M; j ++)
        ans += abs(a[i] - b[j]) * (i - j);

 

Input

多组数据，每组数据

第一行N,M(1 <= N,M <= 50000)

第二行N个数字，a[1].. a[N]

第三行M个数字，b[1]..b[M]

(1 <= a[i],b[i] <= 10000)

Output

每组数据一行，ans

Sample Input

4 41 2 3 45 6 7 8

Sample Output

-40

Hint

you may be TLE if 10000 * 10000 per case
SubmitStatus
　　
　　这一题最简单的思路就是直接枚举，但是这样绝对会TLE,然后稍微优化一下将运算的公式分成两种情况(a[i]>=b[j] || a[i]<b[j])，然后将公式拆开，得到四项，我们可以先预处理出前n项的j,b[j]*j,b[j]的和，然后枚举a[i],求出(a[i]>=b[j] 和 a[i]<b[j])的分界线，然后求两端的和即可。至于求分界线的方法，一种是用lower_bound求，该操作加上枚举a[i]的时间复杂度是O(nlogn)，这样经过试验会超时。另外一种方法是用树状数组求，经小伙伴的测试好像也会超时······。
　　不会超时的方法是除了对b排序以外对a也排个序，然后预处理出每个a[i]的边界loc[i]。这样做的时间复杂度是O(n)，总的时间复杂度是O(nlogn)，不会超时。
 
上代码：
 
 1 /* 2 * this code is made by sineatos 3 * Problem: 1174 4 * Verdict: Accepted 5 * Submission Date: 2014-08-01 12:08:56 6 * Time: 2488MS 7 * Memory: 3240KB 8 */ 9 #include <cstdio>10 #include <cstring>11 #include <utility>12 #include <algorithm>13 #define MAX 5000214 #define ll long long15 using namespace std;16  17 typedef pair<int,int> pii;18  19 pii a[MAX],b[MAX];20 int n,m;21 ll sumb[MAX],sumbj[MAX],sumj[MAX];22 int loc[MAX];23  24 inline ll Sum(int i,int r,int l){25     ll sum=0;26     sum=(ll)a[i].first*a[i].second*(r+1-l) - (ll)a[i].first*(sumj[r]-sumj[l-1]) -(ll)a[i].second*(sumb[r]-sumb[l-1]) + (sumbj[r]-sumbj[l-1]);27     return sum;28 }29  30 int main()31 {32     ll sum;33     //freopen("data.txt","r",stdin);34     while(scanf("%d %d",&n,&m)!=EOF){35         for(int i=1;i<=n;i++){36             scanf("%d",&a[i].first);37             a[i].second=i;38         }39         for(int i=1;i<=m;i++){40             scanf("%d",&b[i].first);41             b[i].second=i;42         }43         sort(a+1,a+n+1);44         sort(b+1,b+m+1);45         sumb[0]=sumbj[0]=sumj[0]=0;46         int k=1;47         for(int i=1;i<=n;i++){48             while(k<=m && a[i].first>=b[k].first) k++;49             loc[i]=k;50         }51         for(int i=1;i<=m;i++){52             sumb[i]=sumb[i-1]+b[i].first;53             sumbj[i]=sumbj[i-1]+(ll)b[i].first*b[i].second;54             sumj[i]=sumj[i-1]+b[i].second;55         }56         sum=0;57         for(int i=1;i<=n;i++){58             int mid=loc[i];59             ll p1=Sum(i,m,mid);60             ll p2=Sum(i,mid-1,1);61             sum+=p2-p1;62         }63         printf("%lld\n",sum);64     }65     return 0;66 }
/*Sum*/

 


联系
我们