POJ 1804

简介: 题目:http://poj.org/problem?id=1804 大意:给你一串数字,排序。求出最少的交换次数  \ 我用归并做的 #include #include using namespace std; int aa[500010],bb[500010]; long lon...

题目:http://poj.org/problem?id=1804

大意:给你一串数字,排序。求出最少的交换次数  \

我用归并做的

#include<iostream>
#include<cstring>
using namespace std;
int aa[500010],bb[500010];
long long  s=0;
void merge(int l,int m,int r)
{
     int i=l,j=m+1,t=0;
     while(i<=m&&j<=r)
     {
          if(aa[i]>aa[j])
          {
               bb[t++]=aa[j++];
               s+=m-i+1;
          }
          else
          {
               bb[t++]=aa[i++];
          }
     }
     while(i<=m)
          bb[t++]=aa[i++];
     while(j<=r)
          bb[t++]=aa[j++];
     for(int i=0;i<t;i++)     //并!不能省,否则归并排序不完整
     {
          aa[l+i]=bb[i];
     }
}
void Msort (int L,int R)   
{
    int cen;
    if(L<R)
    { cen=(L+R)/2;
    Msort(L,cen);
    Msort(cen+1,R);
    merge(L,cen,R);

    }

}
void merge_sort(int *a,int n)
{ Msort(0,n-1);     //做接口;

}
int main()
{
    int n,d=1;
    cin>>n;

    for(int i=0;i<n;i++)
    {   memset(aa,0,sizeof(aa));
        memset(bb,0,sizeof(bb));

       int q;
        cin>>q;

        if(q==0)break;

    for(int j=0;j<q;j++)
    {
        cin>>aa[j];
    }
    merge_sort(aa,q);
cout<<"Scenario #"<<d<<':'<<endl;
    cout<<s<<endl<<endl;
     s=0;d++;

     }
    return 0;

}

 

相关文章
|
12月前
|
机器学习/深度学习 数据采集 人工智能
文档智能 & RAG 让AI大模型更懂业务 —— 阿里云LLM知识库解决方案评测
随着数字化转型的深入,企业对文档管理和知识提取的需求日益增长。阿里云推出的文档智能 & RAG(Retrieval-Augmented Generation)解决方案,通过高效的内容清洗、向量化处理、精准的问答召回和灵活的Prompt设计,帮助企业构建强大的LLM知识库,显著提升企业级文档管理的效率和准确性。
|
11月前
|
数据采集 人工智能 自然语言处理
《文档智能 & RAG让AI大模型更懂业务》解决方案测评
《文档智能 & RAG让AI大模型更懂业务》解决方案测评
|
12月前
|
人工智能 算法
《文档智能 & RAG让AI大模型更懂业务》解决方案测评
本文总结了对某解决方案的实践体验,包括对实践原理的理解、部署过程中的文档帮助、通过文档智能和检索增强生成(RAG)结合构建的LLM知识库的优势体验,以及解决方案适用的业务场景。总体评价积极,但也指出了文档细节和部署流程上的改进建议。
219 0
|
10月前
|
人工智能
SynCamMaster:快手联合浙大、清华等大学推出的多视角视频生成模型
SynCamMaster是由快手科技联合浙江大学、清华大学等机构推出的全球首个多视角视频生成模型,能够结合6自由度相机姿势,从任意视点生成开放世界视频。该模型通过增强预训练的文本到视频模型,确保不同视点的内容一致性,支持多摄像机视频生成,并在多个应用场景中展现出巨大潜力。
202 4
SynCamMaster:快手联合浙大、清华等大学推出的多视角视频生成模型
|
传感器 数据可视化 定位技术
压路机土方压实摊铺精确施工引导系统
压路机土方压实摊铺精确施工引导系统
174 1
|
数据采集 传感器 监控
LabVIEW汽车ECU测试系统
LabVIEW汽车ECU测试系统
180 2
|
移动开发 小程序 JavaScript
uniapp中uview组件库丰富的Slider 滑动选择器的使用方法
uniapp中uview组件库丰富的Slider 滑动选择器的使用方法
1405 1
|
存储 安全 前端开发
深入探讨安全验证:OAuth2.0、Cookie与Session、JWT令牌、SSO与开放授权平台设计
这篇文章讨论了认证和授权的概念,并探讨了设计权限认证框架的原则。它还比较了Cookie和Session的区别,并探讨了处理分布式部署时的Session保存问题。此外,文章还介绍了CSRF攻击及其防范方法,以及OAuth2.0、JWT令牌和SSO的概念。最后,文章提出了设计开放授权平台时需要考虑的因素。
361 0
深入探讨安全验证:OAuth2.0、Cookie与Session、JWT令牌、SSO与开放授权平台设计
|
安全 网络安全 数据库
localhost知识
localhost知识
2123 0
|
编解码
【解决】YOLOv6.1安装requirements.txt报错UnicodeDecodeError: ‘gbk‘ codec can‘t decode byte 0x84
【解决】YOLOv6.1安装requirements.txt报错UnicodeDecodeError: ‘gbk‘ codec can‘t decode byte 0x84
431 0