AtCode nadafes2022_day1 **A - Max Inversion**

标签

• 数学

题目地址

A - Max Inversion

• https://atcoder.jp/contests/nadafes2022_day1/tasks/nadafes2022_day1_a

問題描述

長さ N の攪乱順列の転倒数の最大値を求めてください。

攪乱順列とは、1 $\le$ i $\le$ Nに対して P${}_i$ $\ne$ i を満たす順列のことです。

転倒数とは、1 $\le$ i < j $\le$ Nかつ P${}_i$ > P${}_j$ を満たす整数の組 (i,j)の個数です。

制約

• 入力は全て整数である。
• 2 $\le$ N $\le$10$^9$

入力

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

N

出力

答えを 1 行に出力してください。

入力例 1

3

出力例 1

2

P=(2,3,1) の場合、これは攪乱順列であり、転倒数は 2です。

• （2,1）和（3,1）满足条件，所以是：2

P=(3,2,1)の場合、転倒数が 3 となりますが P${}_2$ = 2 であるためこれは攪乱順列ではありません。

题意

• 求颠倒数数组最大个数，颠倒数满足下面条件
  • 数据颠倒后P${}_i$ $\ne$ i
  • 满足：1 $\le$ i < j $\le$ N 并且 P${}_i$ > P${}_j$ 整数数组 (i,j)的个数

思路

从1开始的整数组，为保证颠倒数最多，越大的值必定越往前放，因为可以保证后面的值基本都小于它

• 如果n为偶数，则可以保证将其倒序后每一位必定不与其本身的值相等

• 如果是奇数，倒序后数组的中间值会与其原来的数字相同，此时将中间值与其相邻的值互换，则保证了利益最大化，即只会减少一种可能性

每一位都有n - i - 1位数字小于它，可用级数求和的公式推算

题解

小码匠

#include <bits/stdc++.h>
#include <cstdlib>

using namespace std;

#define endl '\n';

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // 输入
    long long n;
    cin >> n;
    cout << fixed;
    if(n % 2 == 0) {
        cout << (n - 1) * n / 2;
    } else {
        cout << (n - 1) * n / 2 - 1;
    }

    return 0;
}

参考题解1

• 思路一致

void solve() {
	ll n; 
	cin >> n;
	ll ans = n * (n - 1) / 2;
	if (n % 2) ans--;
	cout << ans << "\n";
}
 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

参考题解2

• 不需要判断奇偶性，一个字，妙！

using ll = long long;
#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res = 0,buf = 0;
  bool judge = true;
  ll n;
  cin >> n;
  cout << n * (n-1) / 2 - n % 2 << endl;
  return 0;
}

复盘

• 数据溢出问题，题目中数据范围：2 $\le$ N $\le$10$^9$
  • 进行乘法运算时，N过大时会超过10位，不能开int，应该定义long long
  • 这是最近两天做题犯的第三次因为开的过小导致提交WA