首页 > 代码库 > acdream1174 合并同类项
acdream1174 合并同类项
这题说的是
给出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); NM【1,50000】 快熟计算出ans 3 秒 当画出这个乘法表后救就会发现 将b[i] 合并，然后合并完同类项就可以做了 效率 mlogn 使用stl的二分还不行卡常数太不合理了
#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>#include <vector>using namespace std;typedef long long ll;const int max_n =100005;struct point{ int v,num; point(ll a=0, ll b=0){ v=a; num=b; } bool operator <(const point A)const { return v<A.v||(v==A.v&&num<A.num); }}P[max_n];int n,m;int B[max_n],A[max_n],K[max_n];ll perAsum[max_n],perAnum[max_n],perAper[max_n];int binser(int n, int v){ int L=0, R =n; while(L<R){ int mid = (L+R)/2; if(K[mid]<=v) L=mid+1; else R=mid; } return L;}int main(){ ll two=2,one =1; int cas=0; /*freopen("data.in","r",stdin); freopen("data.out","w",stdout); */while(scanf("%d%d",&n,&m)==2){ int V; ll num=one*(n-1)*n/two; for(int i=0; i<n; ++i){ scanf("%d",&V); A[i]=V; P[i]=point(V,i); } for(int i=0; i<m; ++i) scanf("%d",&B[i]); ll colu=0,per=0; for(int i =0; i<n; i++){ colu=colu+one*A[i]*i; per=per+A[i]; } ll ans=0; for(int i=0; i<m; ++i){ ans = ans+ colu; colu= colu - per; ans = ans - one*B[i]*num; num = num - n; } sort(P,P+n); perAnum[0]=P[0].num; perAsum[0]=one*P[0].v*P[0].num; perAper[0]=P[0].v; K[0]=P[0].v; for(int i=1; i<n; ++i){ perAnum[i] = perAnum[i-1]+P[i].num; perAsum[i] = perAsum[i-1]+one*P[i].num*P[i].v; perAper[i] = perAper[i-1]+P[i].v; K[i]=P[i].v; } for(int i=0; i<m; ++i){ int loc = binser(n,B[i]); if(loc<=0)continue; loc-=1; ll perA = perAsum[loc]-perAper[loc]*i; ll perB = B[i]*(perAnum[loc]-one*(loc+1)*i); ans = ans - ( perA-perB )*two; } printf("%I64d\n",ans); } return 0;}
acdream1174 合并同类项
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。