UVa 11495 - Bubbles and Buckets
2024-10-19 06:17:37
题目大意:给一个有n个数的序列,通过交换相邻的逆序数使这个序列最终有序,求需要交换的次数。
本来可以用冒泡排序解决,但是n达到105,用冒泡排序会超时,用O(nlogn)的归并排序可以达到要求。《算法竞赛入门经典》第八章的“逆序对数”有详细介绍。
#include <cstdio>
#define MAXN 100000+10 int a[MAXN], tmp[MAXN];
int cnt; void merge_sort(int l, int r)
{
if (r-l == ) return;
int mid = l + (r-l)/;
merge_sort(l, mid);
merge_sort(mid, r);
int p = l, q = mid, k = l;
while (p < mid || q < r)
{
if (q >= r || (p < mid && a[p] < a[q]))
tmp[k++] = a[p++];
else
{
tmp[k++] = a[q++];
cnt += mid - p;
}
}
for (int i = l; i < r; i++)
a[i] = tmp[i];
} int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int n;
while (scanf("%d", &n) && n)
{
for (int i = ; i < n; i++)
scanf("%d", &a[i]);
cnt = ;
merge_sort(, n);
if (cnt % ) printf("Marcelo\n");
else printf("Carlos\n");
}
return ;
}
最新文章
- CSS垂直水平居中方法总结
- GUI 下
- asp.net+nopi生成Excel遇到设置单元格值null问题
- poj题目必做
- 转: ExtJS中xtype一览
- postgresql - mac 启动 关闭 postgresql
- BZOJ1692: [Usaco2007 Dec]队列变换
- 解决Ubuntu14.04下Clementine音乐播放器不能播放wma文件的问题
- sqlserver2008安装出现跨语言
- runtime/KVO等面试题
- 5. c++ 内存管理 C/C++ 内存机制
- VC中如何获取当前时间(精度达到毫秒级)
- ManualResetEvent和AutoResetEvent的区别
- Html在网页、页面中放置Swf、Flash 背景
- 移动端web总结
- CRLF在过滤XSS语句后打Cookie方式
- IO流(一)
- python类型错误:&#39;NoneType&#39; object is not subscriptable
- Nmap使用指南
- 接口(interface)与多态