注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[nbut] 1250 Garfield DN Number  

2012-11-01 22:53:26|  分类: NBUT OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
用暴力肯定超时,这题的题意是用归并求逆序数
  • This problem is pretty easy.
    A[N] is a array contain N(2 <= N <= 10000) integers.
    Garfield define Garfield DN Number as follow:
    There are two integers i, j. 1 <= i < j <= N and the A[i] > [j].
    It means the Garfield DN Number contain two integers.
    Now you have to count all the Garfield DN Numbers. 
  • 输入
  • First line contain a integer T(T <= 100), means the test case.
    For each test case, the first integer N, means the array's length.
    And then, this line follow N integers.
  • 输出
  • For each case, count the sum of Garfield DN Number number;
  • 样例输入
  • 2 2 1 2 3 3 1 2 
  • 样例输出
  • 0 2 
  • 提示
  • 来源
  • monkeyde17


#include<iostream>
using namespace std;
#define MAX 10010

int sr[MAX],tr[MAX];
long long cnt;
void Merge(int low, int mid, int high)
{
int k, j, i = low;
for (j = mid + 1, k = i; i <= mid && j <= high; ++k)
{
if (sr[i] > sr[j])
{
tr[k] = sr[j++];
cnt += mid - i + 1;
}
else
tr[k] = sr[i++];
}
while (i <= mid)
tr[k++] = sr[i++];
while (j <= high)
tr[k++] = sr[j++];
for (i = low; i <= high; ++i)
sr[i] = tr[i];
}


void MSort(int r, int t)
{
int m = (r + t)/2;
if (r < t)
{
MSort(r, m);
MSort(m + 1, t);
Merge(r, m, t);
}

}

void MergeSort(int length)
{
MSort(1, length);
}

int main()
{
int N;
while (scanf("%d", &N) != EOF)
{
while(N--)
{
int n; scanf("%d",&n);
for (int i = 1; i <= n; i++) scanf("%d", sr + i);
cnt = 0;
MergeSort(n);
printf("%lld\n",cnt);
}

}
return 0;

}

/*
归并求逆序数对
样例输入
2
2 1 2
3 3 1 2
样例输出
0
2*/



  评论这张
 
阅读(161)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018