ABC072

[ABC072C] Together

题面翻译

题目

给出一个长度为N，a1，a2，...，aN的整数序列。对于每个1≤i≤N，您有三个选择：1.将1添加到ai， 2.从ai减去1 3.不执行任何操作。在这些操作之后，您选择一个整数X并计算i的数量，使得ai = X. 通过做出最佳选择来最大化这一数量。

限制

1≤x≤10^5

0≤ai≤10^5

且ai是整数

输出

输出最大可能的数使ai = x

样例输入

7 3 1 4 1 5 9 2

10 0 1 2 3 4 5 6 7 8 9

样例输出

4

3

感谢@牧星提供的翻译

题目描述

長さ $ N $ の整数列 $ a_1,a_2,...,a_N $ が与えられます。

各 $ 1 < =i < =N $ に対し、$ a_i $ に $ 1 $ 足すか、$ 1 $ 引くか、なにもしないかの三つの操作からどれか一つを選んで行います。

この操作の後、ある整数 $ X $ を選んで、$ a_i=X $ となる $ i $ の個数を数えます。

うまく操作を行い、$ X $ を選ぶことで、この個数を最大化してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ a_1 $ $ a_2 $ .. $ a_N $

输出格式

うまく操作を行い、$ X $ を選んだ時の $ a_i=X $ なる $ i $ の個数の最大値を出力せよ。

样例 #1

样例输入 #1
7
3 1 4 1 5 9 2
样例输出 #1
4
样例 #2

样例输入 #2
10
0 1 2 3 4 5 6 7 8 9
样例输出 #2
3
样例 #3

样例输入 #3
1
99999
样例输出 #3
1
提示

制約

$ 1 < =N < =10^5 $

$ 0 < =a_i < 10^5 (1 < =i < =N) $

$ a_i $ は整数

Sample Explanation 1

例えば操作後の数列を $ 2,2,3,2,6,9,2 $ とすることができて、$ X=2 $ とすると $ 4 $ を得ることができ、これが最大です。

思路

不难想到，对整个整数序列进行遍历，记当前遍历到的数字为x，开一个桶记录所有的可能，+1、-1、+0。这样在范围内进行遍历取最大值即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
map<ll,ll> m;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        m[x+1]++,m[x-1]++;
        m[x]++;
    }
    ll ans=0;
    for(int i=0;i<=1e5+10;i++){
        ans=max(ans,m[i]);
    }
    cout<<ans;
    return 0;
}

[ABC072D] Derangement

题面翻译

给你一段长为$N$的序列$p$,你每次可以进行操作交换两个相邻的元素
问最少要几次才能满足任意$i\in[1,N],p_i \neq i$

题目描述

$ 1,2,..,N $ からなる順列 $ p_1,p_2,..,p_N $ が与えられます。次の操作を何回か ($ 0 $回でもよい) 行うことが出来ます。

操作: 順列で隣り合う二つの数を選んでスワップする。

何回か操作を行って、任意の $ 1 < =i < =N $ に対して $ p_i ≠ i $ となるようにしたいです。必要な操作の最小回数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ p_1 $ $ p_2 $ .. $ p_N $

输出格式

必要な操作の最小回数を出力せよ。

样例 #1

样例输入 #1
5
1 4 3 5 2
样例输出 #1
2
样例 #2

样例输入 #2
2
1 2
样例输出 #2
1
样例 #3

样例输入 #3
2
2 1
样例输出 #3
0
样例 #4

样例输入 #4
9
1 2 4 9 5 8 7 3 6
样例输出 #4
3
提示

制約

$ 2 < =N < =10^5 $

$ p_1,p_2,..,p_N $ は $ 1,2,..,N $ の順列である。

Sample Explanation 1

$ 1 $ と $ 4 $ を入れ替え、その後 $ 1 $ と $ 3 $ を入れ替えることで $ p $ は $ 4,3,1,5,2 $ となり、これは条件を満たします。これが最小回数なので、答えは $ 2 $ となります。

Sample Explanation 2

$ 1 $ と $ 2 $ を入れ替えれば条件を満たします。

Sample Explanation 3

初めから条件を満たしています。

思路

对整个序列进行遍历，只要发现$p_i=i$的情况，直接与下一个进行交换，为什么可以这样？因为交换后肯定这两个数都不满足$p_i=i$。需要注意的是，最后一个数$a_n$没有办法与下一个数进行交换，所以只能与前一个数进行交换.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
ll a[MAXN];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ll ans=0;
    for(int i=1;i<n;i++){
        if(i==a[i]){
            swap(a[i],a[i+1]);
            ans++;
        }
    }
    if(a[n]==n){
        ans++;
    }
    cout<<ans;
    return 0;
}