题目大意:给一个有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 ;
}

最新文章

  1. CSS垂直水平居中方法总结
  2. GUI 下
  3. asp.net+nopi生成Excel遇到设置单元格值null问题
  4. poj题目必做
  5. 转: ExtJS中xtype一览
  6. postgresql - mac 启动 关闭 postgresql
  7. BZOJ1692: [Usaco2007 Dec]队列变换
  8. 解决Ubuntu14.04下Clementine音乐播放器不能播放wma文件的问题
  9. sqlserver2008安装出现跨语言
  10. runtime/KVO等面试题
  11. 5. c++ 内存管理 C/C++ 内存机制
  12. VC中如何获取当前时间(精度达到毫秒级)
  13. ManualResetEvent和AutoResetEvent的区别
  14. Html在网页、页面中放置Swf、Flash 背景
  15. 移动端web总结
  16. CRLF在过滤XSS语句后打Cookie方式
  17. IO流(一)
  18. python类型错误:&#39;NoneType&#39; object is not subscriptable
  19. Nmap使用指南
  20. 接口(interface)与多态

热门文章

  1. linux自动化构建工具-scons指南
  2. Linux 监控文件事件
  3. UVA699 dfs and map
  4. android4.0蓝牙使能的详细解析(转)
  5. Java回调函数的理解
  6. mysql 本地操作
  7. Quartz定时调度
  8. 前端开发chrome与fireFox浏览器都使用
  9. 一个action读取另一个action里的session
  10. Padding和父子继承宽高之间的关系