PKU 1007

时间:2021-09-19 09:45:47

题名:DNA排序

题意:给定字符串长度、个数,计算每个字符串的逆序数,然后从大到小排列,有兴趣的可以去看下原题。

计算字符串逆序数,然后排序,这里使用了快速排序算法,string释放的时候竟然有问题,直接字符数组吧。

// 1007.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;
class data
{
public:
char s[];
int c;
};
int partion(data a[],int p,int r){
int x = a[r].c; //通常,拿最后一个值,作为预期的中间值
int middle = p; //记录“较小的一段数据”的最大下标。通常这个值在p和r的中间,故起名middle
data *temp=new data;
for (int j = p ; j < r ; j++){
if (a[j].c < x){ memcpy(temp,&a[middle],sizeof(data));
//int temp = a[middle].c;
memcpy(&a[middle],&a[j],sizeof(data));
//a[middle] = a[j];
memcpy(&a[j],temp,sizeof(data));
//a[j] = temp;
middle++;
}
}
//int temp = a[r];
memcpy(temp,&a[r],sizeof(data));
//a[r] = a[middle];
memcpy(&a[r],&a[middle],sizeof(data));
//a[middle] = temp;
memcpy(&a[middle],temp,sizeof(data));
delete temp;
return middle;
} void QuickSort(data a[],int p,int r){
if (p<r){
int q=partion(a,p,r);
QuickSort(a,p,q-);
QuickSort(a,q+,r);
}
} int main(int argc, char* argv[])
{
int slen=,snum=;
cin>>slen>>snum;
int count=;
char temp[]={}; data *d1=new data[snum];
while (count<snum)
{
cin>>temp;
strcpy(d1[count].s,temp);
int bigTimes=;
for (int i=;i<strlen(temp)-;i++)//计算大的次数
{
for (int j=i+;j<strlen(temp);j++)
{
if(temp[i]>temp[j])
bigTimes++; }
}
d1[count].c=bigTimes;
count++;
}
QuickSort(d1,,count-);
for (int i=;i<count;i++)
{
//strcpy(temp,d1[i].s.c_str());
cout<<d1[i].s<<endl;
}
delete []d1;
return ;
}

PKU 1007的更多相关文章

  1. HDU——PKU题目分类

    HDU 模拟题, 枚举1002 1004 1013 1015 1017 1020 1022 1029 1031 1033 1034 1035 1036 1037 1039 1042 1047 1048 ...

  2. SCNU 2015ACM新生赛初赛【1007&period; ZLM的扑克牌】解题报告

            题目链接详见SCNU 2015新生网络赛 1007. ZLM的扑克牌 .         其实我在想这题的时候,还想过要不要设置求最小的排列,并且对于回文数字的话,可以把扑克牌折起来( ...

  3. PKu 2195

    //PKu 2195 回家 By Loli_con Enail : Loli_con@outlook.com /* 题目叙述 ========= 在一个网格图中,有n个人和n个房子.每一个单位时间,每 ...

  4. sicily 1007&period; To and Fro 2016 11 02

    // Problem#: 1007// Submission#: 4893204// The source code is licensed under Creative Commons Attrib ...

  5. 【HDU 1007】Quoit Design

    http://acm.hdu.edu.cn/showproblem.php?pid=1007 最近欧式距离模板题. 用分治大法(分治的函数名用cdq纯属个人习惯_(:з」∠)_) 一开始狂M. 后来判 ...

  6. 最近点对问题 POJ 3714 Raid &amp&semi;&amp&semi; HDOJ 1007 Quoit Design

    题意:有n个点,问其中某一对点的距离最小是多少 分析:分治法解决问题:先按照x坐标排序,求解(left, mid)和(mid+1, right)范围的最小值,然后类似区间合并,分离mid左右的点也求最 ...

  7. poj 1007 DNA Sorting 解题报告

    题目链接:http://poj.org/problem?id=1007 本题属于字符串排序问题.思路很简单,把每行的字符串和该行字符串统计出的字母逆序的总和看成一个结构体.最后把全部行按照这个总和从小 ...

  8. 【BZOJ】 1007&colon; &lbrack;HNOI2008&rsqb;水平可见直线(凸壳)

    http://www.lydsy.com/JudgeOnline/problem.php?id=1007 一开始我贪心的写了下,当然全wa了.. 这题看了题解感觉很简单. 首先什么情况才能看到呢? w ...

  9. HDU 1007 Quoit Design(二分&plus;浮点数精度控制)

    Quoit Design Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) To ...

随机推荐

  1. Bringing the activity to foreground 将activity切换到前台

    今天遇到这个问题,找了很久,网上一些解决方法不够完全.特做此记录: 经测试以下方法不能将在后台运行的activity切换到前台运行! Intent i = new Intent(); i.setCla ...

  2. android学习笔记39——使用原始资源

    原始资源 android中没有专门提供管理支持的类型文件,都被称为原始资源.例如:声音资源... android原始资源存放位置: 1.res/raw,android SDK会处理该目录下的原始资源, ...

  3. HDU 3577 Fast Arrangement &lpar;线段树区间更新&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3577 题意不好理解,给你数字k表示这里车最多同时坐k个人,然后有q个询问,每个询问是每个人的上车和下车 ...

  4. OpenCV 最小二乘拟合方法求取直线倾角

    工业相机拍摄的图像中,由于摄像质量的限制,图像中的直线经过处理后,会表现出比较严重的锯齿.在这种情况下求取直线的倾角(其实就是直线的斜率),如果是直接选取直线的开始点和结束点来计算,或是用opencv ...

  5. Oracle排序

    按照拼音排序 SELECT * FROM TEAM ORDER BY NLSSORT(排序字段,'NLS_SORT = SCHINESE_PINYIN_M') 按照笔画排序 SELECT * FROM ...

  6. 关于IO多路复用的一篇好文

    http://blog.csdn.net/baixiaoshi/article/details/48708347 http://blog.csdn.net/hguisu/article/details ...

  7. 机器学习之支持向量机(四):支持向量机的Python语言实现

    注:关于支持向量机系列文章是借鉴大神的神作,加以自己的理解写成的:若对原作者有损请告知,我会及时处理.转载请标明来源. 序: 我在支持向量机系列中主要讲支持向量机的公式推导,第一部分讲到推出拉格朗日对 ...

  8. CStatic的透明背景方法

    原文链接: http://blog.sina.com.cn/s/blog_4a470fcc01000406.html 这篇文章中有些许错误,不过思路值得借鉴   如果在一个有颜色的窗体中创建一个CSt ...

  9. 让WIN7桌面显示IE图标

    首先新一个文本文件,将以下代码复制到新建文档中.然后保存为IE.reg,右键以管理员权限运行.此时,注册表注册成功.LOOK,IE图标出来了 Windows Registry Editor Versi ...

  10. input聚焦后光标移动至末尾

    var valSrc=obj.val();obj.val(“”).focus().val(valSrc);