cf1234E

![]()

比较常见的题型,应该递推求解

#include<bits/stdc++.h>
#define forn(i, n) for (int i = 0 ; i < int(n) ; i++)
#define fore(i, s, t) for (int i = s ; i < (int)t ; i++)
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pf2(x,y) printf("%d %d\n",x,y)
#define pf(x) printf("%d\n",x)
#define each(x) for(auto it:x)  cout<<it<<endl;
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int maxn=2e6+5;
const int maxm=2e5+5;
const int inf=1e9;
int n,m,a[maxn];
ll ans;
vector<int> g[maxn];
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a[i];
        if(i) ans+=abs(a[i]-a[i-1]);
    }
    for(int i=1;i<m;i++){
        g[a[i]].push_back(a[i-1]);
        g[a[i-1]].push_back(a[i]);
    }
    cout<<ans<<' ';
    for(int i=2;i<=n;i++){
        for(auto x:g[i]) {
            if(x!=i-1 && x!=i) {
                if(x<i) ans-=i-x-1,ans+=x;
                else ans-=x-i,ans+=x-1;
            }
        }
        for(auto x:g[i-1]) {
            if(x!=i && x!=i-1) {
                if(x<i) ans-=x,ans+=i-x-1;
                else ans-=x-1,ans+=x-i;
            }
        }
        cout<<ans<<' ';
    }
    cout<<endl;
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。