HDU DNA Sorting (树状数组求逆序对)-程序员宅基地

这题就是求逆序对然后根据逆序对大小排序

暴力可解！

我选择的是树状数组，这题如果变种，数据过大，或者需要离散化，暴力就不好解决了

这题浪费挺长时间的，主要是t数组忘记清0.。导致后面的数据全部错误

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>

using namespace std;
typedef struct node{
	string s;
	int len;
}node;
int t[1000]={0};
int add(int i,int v){
	while(i<=30) {
		t[i]+=v;
		i+=i&-i;
	}
}
int getsum(int i){
	int sum=0;
	while(i){
		sum+=t[i];
		i-=i&-i;
	}
	return sum;
}
bool cmp(node n1,node n2){
	return n1.len<n2.len;
}
int main(){
	int num;
	cin>>num;
	getchar();
	while(num--){
		int n,m;
		cin>>n>>m;
		node no[100+10];
		
		getchar();
		for(int i=0;i<m;i++){
			int sum=0;
			//cin>>no[i].s;
			for(int i=0;i<30;i++) t[i]=0;
			int len=no[i].s.size();
			string str="";
			for(int j=0;j<n;j++){
				char c;
				cin>>c;
				str+=c;
				add(c-'A'+1,1);
				sum+=j+1-getsum(c-'A'+1);
				//cout<<sum<<endl;
			}
			no[i].len=sum;
			no[i].s=str;
		}
		sort(no,no+m,cmp);
		for(int i=0;i<m;i++){
			cout<<no[i].s<<endl;
		}
	}
	return 0; 
}

本文链接：https://blog.csdn.net/qq_33193309/article/details/78076707

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

bochs 2.2.6 编译和GDB调试_gdb怎么调试bochs-程序员宅基地

文章浏览阅读1.3k次。Table of Contents1 在ubuntu 10.04上面编译bochs 2.2.6遇到了一些编译问题1.1 修改源文件 symbols.cc1.2 安装如下package:1.3 config1.4 make1 在ubuntu 10.04上面编译bochs 2.2.6遇到了一些编译问题symbols.cc: At global scope_gdb怎么调试bochs

机试练习06：poj3349——哈希表应用-程序员宅基地

文章浏览阅读82次。一、题解方法此题不能采用暴力枚举的办法，利用哈希表先将输入数据分类，然后针对key值相同的雪花，再进一步进行细致地判断。key值采取雪花6个arm值加和，进行粗略比较，因为只有在key值相同的前提下，才有可能两个雪花完全一致。如果两个雪花key值相同，再分别比较每一个arm的长度，顺时针、逆时针比较判断二者异同。只要发现存在相同的雪花，就返回结果。二、题解代码 1...

手把手教你配置：Jenkins+Github+Webhook +Nginx自动化打包部署Vue项目_nginx 配置修改 jenkins 自动部署-程序员宅基地

文章浏览阅读1.3k次。前面的话这篇文章记录阿里云服务器的配置。小柒所使用的系统是CentOS.连接服务器进入自己的云服务器 --》进入实例：点击更多，重置自己的密码：重置之后，重启实例。点击远程连接：成功登录之后：安装nginxyum -y install nginx// 检查是否安装成功nginx -v 成功安装：安装好的文件位置：/usr/sbin/nginx：主程序/et..._nginx 配置修改 jenkins 自动部署

web表单注册验证过程及源码_注册表单里面性别代码怎么写-程序员宅基地

文章浏览阅读3.1k次。效果图：第一部分：学习要点：1.核心方法2.option 参数3.工具方法传统的表单提交，需要多次跳转页面，极大的消耗资源也缺乏良好的用户体验。而这款form.js 表单的 Ajax 提交插件将解决这个问题。一．核心方法官方网站：http://ma_注册表单里面性别代码怎么写

OmniGraffle 7 Mac 注册码（仅做记录）_omnigraffle7许可证密钥-程序员宅基地

文章浏览阅读8k次。OmniGraffle 7 Mac 注册码账号：Appked密码：MFWG-GHEB-HYTW-CGHT-CSXU-QCNC-SXU_omnigraffle7许可证密钥

宝塔搭建ECS下载站时Apache httpd访问出现中文路径与文件名乱码问题的解决方法_宝塔下载文件名乱码-程序员宅基地

文章浏览阅读1k次。宝塔搭建ECS下载站时Apache httpd访问出现路径与文件名乱码问题的解决方法_宝塔下载文件名乱码

随便推点

Java项目：基于java+ssm富锦市业余足球联赛管理系统-程序员宅基地

文章浏览阅读271次。足球联赛管理系统主要目的是对足球联赛中心所有的足球联赛信息进行管理，并且合理管理好管理员发布球队、球员和比赛信息，会员浏览查看球队和比赛信息的流程。提高足球联赛管理的工作效率，降低管理的成本。本系统选用Windows作为服务器端的操作系统，开发语言选用Java，数据库选用Mysql，SSM(Spring+SpringMVC+MyBatis)框架,使用mybatis数据库连接技术，使用eclipse作为系统应用程序的开发工具，Web服务器选用Tomcat版本。下面分别简单阐述一下这几个功能模块需求。1.登