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\ne i$

题目描述

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

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

何回か操作を行って、任意の $1<=i<=N$ に対して $p_i\ne 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;
}