Codeforces 903D - Almost Difference 前缀和+map

xiaoxiao2021-02-28  28

题意:

求:每个数和他前面的数,跟他差值大于一的数的差值的和

思路:

对于每一个数ai,减去他之前的所有的数和,这样的话 有一部分会多减,就是跟这个数差值是一的数,

这样我们再记录每一个数的数量,可以知道ai+1 和 ai-1 的数目,再相应的加上减去个数就是了

#include<iostream> #include<algorithm> #include<iomanip> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<set> #include<queue> #include<stack> #include<map> #define PI acos(-1.0) #define in freopen("in.txt", "r", stdin) #define out freopen("out.txt", "w", stdout) #define kuaidian ios::sync_with_stdio(0); using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 2e5 + 7, maxd = 1e8; const ll mod = 1e9 + 7; const int INF = 0x7f7f7f7f; int n; ll sum[maxn]; map<ll , int> mp; int main() { kuaidian; mp.clear(); cin >> n; long double ans = 0; for(int i = 1; i <= n; ++i) { ll x; cin >> x; ans += ( (long double)(x*(i-1)) - (long double)(sum[i-1]) ); if(mp[x-1]) ans -= (long double)(mp[x-1]); if(mp[x+1]) ans += (long double)(mp[x+1]); sum[i] = sum[i-1] + x; mp[x]++; } cout << fixed << setprecision(0) << ans << endl; return 0; }

转载请注明原文地址: https://www.6miu.com/read-1650365.html

最新回复(0)