当前位置: 代码迷 >> 综合 >> ACdream P1174 Sum
  详细解决方案

ACdream P1174 Sum

热度:10   发布时间:2023-12-21 07:46:25.0

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;
}

方法一般,想上进的同学可以去探求更快的方法。出题者卡了个常数来卡我这种做法,但是我机智地用了输入挂破解了,求管理员继续卡啊!你要再卡常数这道题就没意思了,题目出的不够好请别用卡常数这种低级无聊手段让我们臣服。