Sum
Time Limit: 6000/3000MS (Java/Others)
Memory Limit: 128000/64000KB (Java/Others)
Submit Statistic Next Problem
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 4 1 2 3 4 5 6 7 8
Sample Output
-40
Hint
you may be TLE if 10000 * 10000 per case
Source
classical
Manager
scaucontest
刚做的一道水题，趁热写一发题解。
这题先考虑没有ABS的情况(ai-bj)*(i-j)把这之类所有式子都写出，然后合并同类项，可得a数组的项数符合-m(m-1)/2为首项，差为m的等差数列，b数组同理。
再考虑有了绝对值怎么办，有了绝对值无非是一些小于bj的ai项数（bj类似）出现了变动，故先排序，这样就可以清楚求出那些ai碰到了哪些bj，发生相应的项数变动。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#define rep(i,n) for(i=1;i<=n;i++)
#define MM(a,t) memset(a,t,sizeof(a))
#define INF 1e9
typedef long long ll;
#define mod 1000000007
using namespace std;
ll ans;
struct node{
ll val,index;
char zl;
}a[100002];
ll cnta[50002],cntb[50002];
ll n,m;
void setup(){
<span style="white-space:pre"> </span>ll i,j;
<span style="white-space:pre"> </span>ll tmp;
<span style="white-space:pre"> </span>
<span style="white-space:pre"> </span>cnta[1]=-(m*(m-1)/2);
<span style="white-space:pre"> </span>for(i=2;i<=n;i++)
<span style="white-space:pre"> </span> cnta[i]=cnta[i-1]+m;
cntb[1]=-(n*(n-1)/2);
for(i=2;i<=m;i++)
cntb[i]=cntb[i-1]+n;
}
bool cmp1(node a1,node a2){
<span style="white-space:pre"> </span>return a1.val<a2.val;
}
ll ReadInt()//输入挂
{
char ch = getchar();
ll data = 0;
while (ch < '0' || ch > '9')
ch = getchar();
do
{
data = data*10 + ch-'0';
ch = getchar();
} while (ch >= '0' && ch <= '9');
return data;
}
int main()
{
<span style="white-space:pre"> </span>ll i,j;
<span style="white-space:pre"> </span>
<span style="white-space:pre"> </span>while(scanf("%lld%lld",&n,&m)!=EOF){
<span style="white-space:pre"> </span>setup(); ans=0;
<span style="white-space:pre"> </span>rep(i,n){
<span style="white-space:pre"> </span>ll tmp;
<span style="white-space:pre"> </span>tmp=ReadInt();
<span style="white-space:pre"> </span>a[i].zl='a';
<span style="white-space:pre"> </span>a[i].val=tmp;
<span style="white-space:pre"> </span>a[i].index=i;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>for(i=n+1;i<=n+m;i++){
<span style="white-space:pre"> </span>ll tmp;
<span style="white-space:pre"> </span>tmp=ReadInt();
<span style="white-space:pre"> </span>a[i].zl='b';
<span style="white-space:pre"> </span>a[i].val=tmp;
<span style="white-space:pre"> </span>a[i].index=i-n;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>sort(a+1,a+n+m+1,cmp1);
<span style="white-space:pre"> </span>ll s1=0,sum1=0;
<span style="white-space:pre"> </span>rep(i,n+m)
<span style="white-space:pre"> </span>if(a[i].zl=='a'){
<span style="white-space:pre"> </span> s1+=1; sum1+=a[i].index;<span style="white-space:pre"> </span>
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>else cntb[a[i].index]+=2*(sum1-s1*a[i].index);
<span style="white-space:pre"> </span>s1=0; sum1=0;
<span style="white-space:pre"> </span>for(i=n+m;i>=1;i--)
<span style="white-space:pre"> </span>if(a[i].zl=='b'){
<span style="white-space:pre"> </span>s1+=1; sum1+=a[i].index;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>else cnta[a[i].index]-=2*(s1*a[i].index-sum1);
<span style="white-space:pre"> </span>rep(i,n+m)
<span style="white-space:pre"> </span>if(a[i].zl=='a') ans+=cnta[a[i].index]*a[i].val;
<span style="white-space:pre"> </span>else ans+=cntb[a[i].index]*a[i].val;
<span style="white-space:pre"> </span>printf("%lld\n",ans);
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>
<span style="white-space:pre"> </span>return 0;
}方法一般，想上进的同学可以去探求更快的方法。出题者卡了个常数来卡我这种做法，但是我机智地用了输入挂破解了，求管理员继续卡啊！你要再卡常数这道题就没意思了，题目出的不够好请别用卡常数这种低级无聊手段让我们臣服。