首页 / 算法 / HDU 3743 Frosh Week （归并排序）

HDU 3743 Frosh Week （归并排序）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了HDU 3743 Frosh Week （归并排序），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2085字，纯文字阅读大概需要3分钟。

内容图文

Frosh Week

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1919    Accepted Submission(s): 619

Problem Description
During Frosh Week, students play various fun games to get to know each other and compete against other teams. In one such game, all the frosh on a team stand in a line, and are then asked to arrange themselves according to some criterion, such as their height, their birth date, or their student number. This rearrangement of the line must be accomplished only by successively swapping pairs of consecutive students. The team that finishes fastest wins. Thus, in order to win, you would like to minimize the number of swaps required.
 

Input
The first line of input contains one positive integer n, the number of students on the team, which will be no more than one million. The following n lines each contain one integer, the student number of each student on the team. No student number will appear more than once. 
 

Output
Output a line containing the minimum number of swaps required to arrange the students in increasing order by student number. 
 

Sample Input
            
3
3
1
2
 

Sample Output
            
2
 

同样是个归并排序算逆序对的题目，根poj2299一个样，但是我一开始弄错了，原因是测试数据有好些组，所以得用while(scanf("%d",&n)!=EOF)才行。 
#include<iostream>
using namespace std;
#define M 1000010
int a[M];
int aux[M];
long long int ans;
void merge(int a[],int l,int mid,int h)
{
    int i=l;
    int j=mid+1;
    for(int k=l;k<=h;++k)
        aux[k]=a[k];
    for(int k=l;k<=h;++k)
    {
        if(i>mid)a[k]=aux[j++];
        else if(j>h)a[k]=aux[i++];
        else if(aux[i]>aux[j])
        {
            a[k]=aux[j++];
            ans+=mid-i+1;
        }
        else
            a[k]=aux[i++];
    }
}
void sort(int a[],int l,int h)
{
    if(l>=h)return ;
    int mid=l+(h-l)/2;
    sort(a,l,mid);
    sort(a,mid+1,h);
    merge(a,l,mid,h);
}
int main(int argc, char *argv[])
{
   // freopen("3743.in","r",stdin);
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(a,0,sizeof(a));
        memset(aux,0,sizeof(aux));
        int i=0;
        while(n--)
        {
            scanf("%d",&a[i++]);
        }
        ans=0;
        sort(a,0,i-1);
        printf("%lld\n",ans);
    }
    return 0;
}



原文：http://blog.csdn.net/wdkirchhoff/article/details/41820229

内容总结

以上是互联网集市为您收集整理的HDU 3743 Frosh Week （归并排序）全部内容，希望文章能够帮你解决HDU 3743 Frosh Week （归并排序）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1072268.html

来源：【匿名】