首页 > 其他分享 >UVA - 10716 Evil Straw Warts Live 贪心

UVA - 10716 Evil Straw Warts Live 贪心

时间:2023-04-07 11:08:20浏览次数:41  
标签:count right Straw ++ Evil int Live str left


题目大意:给出一串字符串,问这串字符串是不是回文字符串,如果是的话需要移动几步

解题思路:判断是不是回文,只需要判断里面的字母的个数,如果奇数字符出现超过了1个,那个这个就不是回文字符串了。接下来是移动,应该由外向里移动,不管是先移动那个字符,最后移动的步数都是一样的,所以从前往后扫描,判断一下最短的移动距离,然后移动,每移动一个,count++

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 100 + 5;

char str[maxn];
int judge[28],vis[maxn],len,count,test;
bool flag;
int main() {
	scanf("%d", &test);
	getchar();

	while(test--) {	
		count = 0,flag = false;
		scanf("%s",str);
		len = strlen(str);

		memset(judge,0,sizeof(judge));

		for(int i = 0 ; i < len ; i++) {
			judge[str[i]-'a']++;
		}

		for(int i = 0; i < 26; i++) 
			if(judge[i] % 2 != 0) {
				count++;	
				if(count > 1) {
					flag = true;
					break;
				}
			}

		if(flag){
			printf("Impossible\n");
			continue;
		}
		else {
			int left = 0, right = len - 1, cnt = 0;	
			while(left < right) {
				int lcur = left, rcur = right, temp , Min = 0x3f3f3f3f;
				memset(vis,0,sizeof(vis));
				for(int i = left ; i < right; i++)
					if(!vis[i]) {
						vis[i] = 1;
						int lastcur = i;
						for(int j = i + 1; j <= right; j++)
							if(str[i] == str[j]) {		
								vis[j] = 1;
								lastcur = j;
							}
						temp = i - left + right - lastcur;		
						if(temp < Min) {
							Min = temp;	
							lcur = i;
							rcur = lastcur;	
						}
					}	

				for(int i = lcur; i > left; i--) {
					swap(str[i],str[i-1]);
					cnt++;
				}
				for(int i = rcur; i < right; i++) {
					swap(str[i],str[i+1]);
					cnt++;
				}
				left++;
				right--;
			}	
			printf("%d\n",cnt);
		}
	}
	return 0;
}



标签:count,right,Straw,++,Evil,int,Live,str,left
From: https://blog.51cto.com/u_10970600/6175562

相关文章

  • 使用open live writer客户端写博客(亲测有效)
    博客都开了这么久了,才开始将资料上传,但是每次都要登录网页确实很麻烦,所以就用openlivewriter,使用起来真的是挺方便的,所以将我在安装配置时,发现的问题汇总起来以便日后再次碰到忘记怎么处理了,哈哈,我记性不好 一:安装                              ......
  • keepalived+MySQL实现高可用
    (一)keepalived概述Keepalived通过VRRP(虚拟路由冗余协议)协议实现虚拟IP的漂移。当master故障后,VIP会自动漂移到backup,这时通知下端主机刷新ARP表,如果业务是通过VIP连接到服务器的,则此时依然能够连接到正常运行的主机,RedHat给出的VRRP工作原理如下图: 本来对VIP漂移有一定了解的......
  • 配置keepalived和LVS的DR模式双机热备
    步骤:Firewalld防火墙配置IP地址,LVS主服务器和从服务器配置IP地址修改内核参数,配置web服务器IP地址,配置NFS共享存储服务器IP地址,客户端配置IP地址搭建共享存储配置允许web服务器连接当前NFS存储服务器,安装配置网站服务器连接共享存储安装配置keepalived加LVS的DR模式双机热备配置LVS......
  • Jetpack—LiveData组件的缺陷以及应对策略
    一、前言为了解决Android-App开发以来一直存在的架构设计混乱的问题,谷歌推出了Jetpack-MVVM的全家桶解决方案。作为整个解决方案的核心-LiveData,以其生命周期安全,内存安全等优点,甚至有逐步取代EventBus,RxJava作为Android端状态分发组件的趋势。官网商城app团队在深度使用LiveData的......
  • LIVE555再学习 -- testOnDemandRTSPServer 源码分析
    一、简介先看一下官网上的介绍:testOnDemandRTSPServer createsaRTSPserverthatcanstream,viaRTPunicast,fromvarioustypesofmediafile,ondemand.(Supportedmediatypesinclude:MPEG-1or2audioorvideo(elementarystream),includingMP3audio;MPEG-4......
  • LIVE555再学习 -- 单播、多播、广播、直播、点播 都是个啥?
    上一篇文章提到单播、多播。但是这是什么意思?接下来我们看一下。参看:搜狗--单播参看:维基百科——单播一、单播简介    Unicast,是客户端与服务器之间的点到点连接。“点到点”指每个客户端都从服务器接收远程流。仅当客户端发出请求时,才发送单播流。Unicast(单播):在客......
  • LIVE555再学习 -- testRTSPClient 实例
    上一篇文章简单看了一遍 testRTSPClient 的源码,接下来举几个应用实例加深一下。首先什么都不做修改,先执行一遍,看一下。一、执行 testRTSPClient 特么,上面的东西我没看明白。。。a=、b=、c=等等这是什么?还有我看别人分析的好像用到什么网络抓包工具,我不知道是什么工具,可能是......
  • LIVE555再学习 -- testH264VideoStreamer 源码分析
    上一篇文章我们已经讲了一部分:testH264VideoStreamer重复从H.264基本流视频文件(名为“test.264”)中读取,并使用RTP多播进行流式传输。 该程序还具有内置的RTSP服务器。Apple的“QuickTime播放器”可用于接收和播放此音频流。要使用它,让玩家打开会话的“rtsp://”URL(程序在......
  • LIVE555再学习 -- testRTSPClient 源码分析
    现在开讲 testRTSPClient。在官网这这样一段介绍,参看:RTSPclient翻译下来就是:testRTSPClient是一个命令行程序,显示如何打开和接收由RTSPURL指定的媒体流,即以rtsp://开头的URL在这个演示应用中,接收到的音频/视频数据什么也没有。但是,您可以在自己的应用程序中使用和调整此代码(......
  • LIVE555再学习 -- Windows 下编译
    然后开始下载编译,其中包含,Windows、Linux和交叉编译三种形式。首先来讲Windows下编译参看:Live555研究之一源代码编译一、下载源码下载:Indexof/liveMedia/public参看:LIVE555StreamingMedia选择下载live555-latest.tar.gz二、文件介绍我的开发环境为win1064位+VS2017将上面......