[CF903D]Almost Difference

题目链接：https://codeforces.com/problemset/problem/903/D

题意：

给出一个函数d(x,y) ，然后有n个数a1,a2,...,an 求出d(ai,aj)的和（1<=i<j<=n）

分析：

先默认d(x,y)=y-x;

然后对于第i位的数字，就会作为x n-i次，作为 y i-1次

所以sum是 Σ(n-i)*ai*(-1) + Σ(i-1)*ai;

然后|x-y|<=1特殊处理：

　　d(ai-1,ai)=1;d(ai+1,ai)=-1;

记录到当前i的时候，ai-1和ai+1出现的次数

然后对应到sum进行-1和+1就可以了

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 
 5 double a[200005];
 6 int n;
 7 long double sum;//要用longdouble 
 8 map<double,double>appear;
 9 
10 int main(){
11     cin>>n;
12     for(int i=1;i<=n;i++){
13         cin>>a[i];
14     }
15 /*    int appear[maxn+3];
16     memset(appear,0,sizeof(appear));之前不咋会用map*/
17     for(int i=1;i<=n;i++){
18         sum+=(i-1)*a[i];
19         sum-=(n-i)*a[i];
20         appear[a[i]]++;//记录每个在当前i出现的次数
21         sum-=appear[a[i]-1];
22         sum+=appear[a[i]+1];//这俩都是ai作为y的时候
23     }
24     cout<<fixed<<setprecision(0)<<sum;
25 //cout输出小数点后几位的方法
26 }

我是fw

这么简单都卡住了

回头写一些cout 的一些相关操作以及 map的用法

先码俩大佬的博客在这，回头自己写一个

map的用法

https://blog.csdn.net/google19890102/article/details/51720305

cout

https://blog.csdn.net/qq_35040828/article/details/65453266?readlog

原文链接: https://www.cnblogs.com/Danzel-Aria233/p/12964666.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/351025

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

[CF903D]Almost Difference

相关推荐