Frosh Week
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 289 Accepted Submission(s): 72
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
Sample Output
此题大意:与上题一样,求逆序数,不要给英文骗到。我想练下写离散化,所以再写一次,印象更深刻。
链接:http://acm.hdu.edu.cn/showproblem.php?pid=3743
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
int n, a[1000005];
struct node
{
int num, id;
}ch[1000005];
bool cmp1(node a, node b)
{
return a.num < b.num;
}
bool cmp2(node a, node b)
{
return a.id < b.id;
}
int lowbit(int i)
{
return i&(-i);
}
void update(int i, int x)
{
while(i <= n)
{
a[i] += x;
i += lowbit(i);
}
}
int sum(int i)
{
int sum = 0;
while(i > 0)
{
sum += a[i];
i -= lowbit(i);
}
return sum;
}
int main()
{
int i;
long long ans; //注意要long long!!!
while(scanf("%d", &n) != EOF)
{
ans = 0;
memset(a, 0, sizeof(a));
for(i = 1; i <= n; i++)
{
scanf("%d", &ch[i].num);
ch[i].id = i;
}
///离散化
sort(ch+1, ch+n+1, cmp1); //按值排序
ch[1].num = 1; //直接把他的值改变离散化
for(i = 2; i <= n; i++)
{
if(ch[i].num != ch[i-1].num)
ch[i].num = i;
else ch[i].num = ch[i-1].num;
}
sort(ch+1, ch+n+1, cmp2); //再按id排序
///离散化完毕
for(i = 1; i <= n; i++)
{
update(ch[i].num, 1);
ans += (sum(n) - sum(ch[i].num));
}
printf("%I64d\n", ans);
}
return 0;
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
acm hdu as easy as a+b
应同学之邀帮忙发布的一篇勘误 【HDU 3993】田忌赛马 题解+勘误 题解这里就略写一下了,主要是勘误。 这道题是2011年之前的多校...数据很小,可以考虑状态压缩+记忆化搜索 直接定义二维状态有很多浪费的空间,可以考虑u
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
杭电OnlineJudge 200-2099的解题报告
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)