首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >AtCode nadafes2022_day1 A - Max Inversion

AtCode nadafes2022_day1 A - Max Inversion

作者头像
小码匠
发布2022-06-16 17:57:13
发布2022-06-16 17:57:13
3050
举报

AtCode nadafes2022_day1 A - Max Inversion

标签

  • 数学

题目地址

A - Max Inversion

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

問題描述

入力

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

代码语言:javascript
复制
N

出力

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

入力例 1

代码语言:javascript
复制
3

出力例 1

代码语言:javascript
复制
2

思路

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

  • 如果n为偶数,则可以保证将其倒序后每一位必定不与其本身的值相等
  • 如果是奇数,倒序后数组的中间值会与其原来的数字相同,此时将中间值与其相邻的值互换,则保证了利益最大化,即只会减少一种可能性

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

题解

小码匠

代码语言:javascript
复制
#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

  • 思路一致
代码语言:javascript
复制
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

  • 不需要判断奇偶性,一个字,妙!
代码语言:javascript
复制
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
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-05-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 小码匠和老码农 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • AtCode nadafes2022_day1 A - Max Inversion
  • 标签
  • 题目地址
  • 問題描述
    • 入力
    • 出力
    • 入力例 1
    • 出力例 1
  • 思路
  • 题解
    • 小码匠
    • 参考题解1
    • 参考题解2
  • 复盘
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档