首页 > 代码库 > hust 1347 - Reverse Number

hust 1347 - Reverse Number

2024-07-09 00:45:33   220人阅读

题目描述

Given a non-negative integer sequence A with length N, you can exchange two adjacent numbers each time. After K exchanging operations, what’s the minimum reverse number the sequence can achieve? The reverse number of a sequence is the number of pairs (i, j) such that i < j and Ai > Aj

输

入There are multiple cases. For each case, first line contains two numbers: N, K 2<=N<=100000, 0 <= K < 2^60 Second line contains N non-negative numbers, each of which not greater than 2^30

输出

Minimum reverse number you can get after K exchanging operations.

样例输入

3 13 2 15 25 1 4 3 2

样例输出

Case #1: 2Case #2: 5

本题当然是先求逆序对，归并排序，树状数组，线段树，什么都可以，主要是先求出来，做k次变化，我们的目标不就是找刚好是逆序的变换，这样再看看k是否大于逆序对数的情况，不就完了
#include<map>#include<set>#include<queue>#include<cmath>#include<vector>#include<cstdio>#include<string>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define  inf 0x0f0f0f0fusing namespace std;const int maxn=100000+10;int a[maxn],b[maxn],ans;void merge_sort(int* A,int x,int y,int*T){     if (y-x>1)     {          int m=x+(y-x)/2;          int p=x, q=m, i=x;          merge_sort(A,x,m,T);          merge_sort(A,m,y,T);          while (p<m || q<y)          {               if (q>=y || (p<m && A[p]<=A[q])) T[i++]=A[p++];               else {T[i++]=A[q++];ans+=m-p;}          }          for (int i=x;i<y;i++) A[i]=T[i];     }}int main(){     int n,k,t=0;     while(scanf("%d%d",&n,&k)!=EOF)     {          t++;          for (int i=0;i<n;i++) scanf("%d",&a[i]);          ans=0;          merge_sort(a,0,n,b);          ans-=k;          bool cut=false;          for (int i=0;i<n-1;i++) if (a[i]==a[i+1]) {cut=true;break;}          if (ans<0)          {               if ((-ans)%2==0) ans=0;               else               {                    if(cut) ans=0;                    else ans=1;               }          }          printf("Case #%d: %d\n",t,ans);     }     return 0;}

作者 chensunrise


联系
我们