首页 > 其他分享 >B. Minimize Inversions

B. Minimize Inversions

时间:2024-02-28 16:12:44浏览次数:31  
标签:排列 Minimize int 升序 Inversions 对数 unit 逆序

原题链接

题解

逆序对数最小的排列是严格升序的排列,因此我猜想有一个严格升序的排列最优的
证明;
冒泡排序,我们把排列a中最大的元素不断地往右作相邻对换,这样一来,序列a的逆序对数必定减少一,序列b的逆序对数可能减少一,可能不变,可能加一,但是两个排列的总逆序对数不可能增加。
然后再逆着想验证了这种策略的可行性

codee

#include<bits/stdc++.h>
using namespace std;
struct unit
{
    int x,y;
}a[200005];
bool cmp(unit x,unit y)
{
    return x.x<y.x;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i].x;
        for(int i=1;i<=n;i++) cin>>a[i].y;
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++) cout<<a[i].x<<" ";
        puts("");
        for(int i=1;i<=n;i++) cout<<a[i].y<<" ";
        puts("");
    }
    return 0;
}

标签:排列,Minimize,int,升序,Inversions,对数,unit,逆序
From: https://www.cnblogs.com/pure4knowledge/p/18040737

相关文章

  • Minimize Inversions
    先来看看官方题解的做法,他一反常态的没有在逆序对题目里面考虑每个位置的贡献,而是直接回到定义考虑每对数是否是逆序对我们考虑原数列中任意的一组数\((a_i,a_j)\)和\((b_i,b_j)\)。如果最开始两个都不是逆序对,那么交换之后两个都是逆序对;如果最开始两个都是逆序对,那么交换之后两......
  • Minimize OR of Remaining Elements Using Operations
    MinimizeORofRemainingElementsUsingOperationsYouaregivena 0-indexed integerarray nums andaninteger k.Inoneoperation,youcanpickanyindex i of nums suchthat 0<=i<nums.length-1 andreplace nums[i] and nums[i+1] withas......
  • D. Yet Another Inversions Problem
    D.YetAnotherInversionsProblemYouaregivenapermutation$p_0,p_1,\ldots,p_{n-1}$ofoddintegersfrom$1$to$2n-1$andapermutation$q_0,q_1,\ldots,q_{k-1}$ofintegersfrom$0$to$k-1$.Anarray$a_0,a_1,\ldots,a_{nk-1}$oflength$n......
  • [Codeforces] CF1591C Minimize Distance
    CF1591CMinimizeDistance题目一条线上有\(n\)(\(1\len\le2\cdot10^5\))个仓库,第\(i\)个仓库的位置是\(x_i\)(\(1\lei\len\))。你有\(n\)箱货物,要分别运到这\(n\)个仓库里。你的初始位置在点\(0\),一次可以携带\(k\)(\(1\lek\len\))箱货物。在送完携带......
  • AtCoder Grand Contest 023 E Inversions
    洛谷传送门AtCoder传送门首先将\(a\)从小到大排序,设\(p_i\)为排序后的\(a_i\)位于原序列第\(p_i\)个位置,\(x_i\)为要填的排列的第\(i\)个数。设\(A=\prod\limits_{i=1}^n(a_i-i+1)\),则\(A\)为排列的总方案数(考虑按\(a_i\)从小到大填即得)。套路地,统......
  • 题解 P5426 [USACO19OPEN]Balancing Inversions G
    来一篇简单易懂的良心题解。由于数值不是\(0\)就是\(1\),我们可以考虑将逆序对的统计方式化简。以左区间为例,设\(x\)为\(1\)的个数,\(p_i\)为第\(i\)个\(1\)的坐标,则逆序对个数为\(\sum\limits_{i=1}^{x}n-p_i-(x-i)\)。也就是\((n-x)\cdotx+\frac{x\cdot(x+1)}{......
  • CF1637H Minimize Inversions Number
    我直接??????????????????考虑一个数怎么做,就是逆序对减去一个\(i\)前面的逆序对再加上顺序对。考虑很多数怎么做,就是这个玩意的和再加上子序列种的顺序对减去逆序对,顺序对可以用逆序对表示,现在只考虑顺序对。注意到,如果\(i<j,p_i>p_j\)且\(i\)在子序列中\(j\)不在子序列中,那么把\(j\)弄......
  • 「解题报告」AGC023E Inversions
    好。首先考虑怎么计算方案数。我们考虑按照\(a_i\)从小往大选,设排序后的下标为\(b_i\),那么容易得出方案数为:\[s=\prod_{i=1}^n(a_{b_i}-i+1)\]我们设\(c_i=a_{b_i}-i+1\),这代表着某个数的选择方案数。然后考虑经典拆贡献,枚举每一对\((i,j)\),求\(p_i>p_j......
  • Educational Codeforces Round 75 C Minimize The Integer
    这道题的意思就是给出一个由数字组成的字符串,相邻的数字可以互换位置,但是如果相邻的为同奇同偶这样就不能交换。让我们求交换任意次数可以产生的最小数。这条限制就是说......
  • 1877.minimize-maximum-pair-sum-in-array 数组中最大数对和的最小值
    问题描述1877.数组中最大数对和的最小值解题思路贪心将数组从小到大排序,最小最大配对,次小次大配对,依次配对,结果就是这些配对和的最大值。代码classSolution{publi......