HDU-4911 Inversion(正規順序で逆順序を求める)
1364 ワード
問題を見ます
長さnのシーケンスを一つあげて、最大k回の2つの交換(隣の数の間だけ)を経て、少なくともどれぐらいの逆順がありますか?
分析:総和の逆順対数を求め、その後ans=max(求めた総逆順は-k、0)である.
わぁ、Anything is possible.
参照コード:
長さnのシーケンスを一つあげて、最大k回の2つの交換(隣の数の間だけ)を経て、少なくともどれぐらいの逆順がありますか?
分析:総和の逆順対数を求め、その後ans=max(求めた総逆順は-k、0)である.
わぁ、Anything is possible.
参照コード:
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
int n;
LL k;
int a[maxn];
int tmp[maxn];
LL ans;//emmmmmm LL
void Merge( int l, int mid, int r)
{
int i = l;
int j = mid+1;
int k = l;
while( i <= mid && j <= r)
{
if( a[i] > a[j])
{
tmp[k++] = a[j++];
ans += mid-i+1;
}
else
tmp[k++] = a[i++];
}
while( i <= mid)
tmp[k++] = a[i++];
while( j <= r)
tmp[k++] = a[j++];
for( int i = l; i <= r; i++)
a[i] = tmp[i];
}
void MergeSort( int l, int r)
{
if( l < r)
{
int mid = (l+r)>>1;
MergeSort(l,mid);
MergeSort(mid+1,r);
Merge(l,mid,r);
}
}
int main()
{
while( ~scanf("%d%lld",&n,&k))
{
for( int i = 0; i < n; i++)
scanf("%d",&a[i]);
ans = 0;
MergeSort(0,n-1);
printf("%lld
",max(0LL,ans-k));
}
return 0;
}