ACM-Position Arrangement (解题报告)

Time Limit:1000MS Memory Limit:32768K

Description:

一个01串,我们可以对相邻两个字符实行交换位置的操作. 求最少的操作次数使得所有的1的位置连续. eg. s="010110",swap(s[1],s[2])之后,变成"001110". 所以答案是1.

Input:

多组数据,每组数据一个01字符串.串长不超过10^5

Output:

首先输出Case #k: ,然后是答案.

Sample Input:

010110
10101100
000

Sample Output:

Case #1: 1
Case #2: 3
Case #3: 0

Source:

Status Submit

题目链接：http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1703

－－－－－－－－－－－－－－－－－－－－－分割线－－－－－－－－－－－－－－－－－－－－－－－－－－

#include<stdio.h>

char szStr[100005] ;

int FindMinStep(int nOneSum, int nZeroSum , int nIndex) ;

int main(void)
{
	int fFindOne = 0 ;
	int fFindZero = 0 ;
	int nMinToLeft = 0 ;
	int nMinToRight = 0 ;
	int nMinStep = 0 ;
	int nOneFwSum = 0 ;		//0前面的1，比如110001，指的是11
	int nOneBhSum = 0 ;		//0后面的1，比如11000111，指的是111
	int nZeroSum = 0 ;
	int i = 0 ;
	int j = 1 ; 
	
	while(scanf("%s",szStr) != EOF)
	{	
		fFindOne = fFindZero = -1 ;
		nMinToLeft = nMinToRight = nMinStep = 0 ;
		nOneFwSum = nOneBhSum = nZeroSum = 0 ;
		i = 0 ;
		
		while(szStr[i] != '\0')
		{
			if('1' == szStr[i])
			{			
				fFindOne = 1 ;
				
				if(fFindZero > 0)
				{
					nOneBhSum++ ;
					if('0' == szStr[i+1] || '\0' == szStr[i+1])
					{					
						nMinToLeft = nOneBhSum*nZeroSum + FindMinStep(nOneFwSum+nOneBhSum,nZeroSum,i+1) ;		//向左决策
						nMinToRight = nOneFwSum*nZeroSum +  FindMinStep(nOneFwSum+nOneBhSum,0,i+1) ;			//向右决策
						
						nMinStep = nMinToLeft < nMinToRight ? nMinToLeft : nMinToRight ;		//左右分支中最少步数
						break ;
					}	
				}
				else
				{
					nOneFwSum++ ;
				}		
			}
			else if('0' == szStr[i])
			{
				if(fFindOne > 0 )
				{		
					nZeroSum++ ;
					fFindZero = 1 ; 
				}
			}
			i++ ;
		}
		printf("Case #%d: %d\n",j,nMinStep) ;
		j++ ;
	}	    
	
	return 0 ;
}

//参数的意义分别是：此时已经合并1的数目、与下一个1串相隔多少个0、此时在01串的下标
int FindMinStep(int nOneSum, int nZeroSum , int nIndex)	
{
	int i = nIndex ;
	int fFindZero = 1 ;
	int nMinToLeft = 0 ;
	int nMinToRight = 0 ;
	int nMinStep = 0 ;
	int nOneFwSum = nOneSum ; 
	int nOneBhSum = 0 ;
	int nZeroThisSum = nZeroSum ;
	
	if('\0' == szStr[nIndex])
	{
		return 0 ;
	}
	else
	{	
		while(szStr[i] != '\0')
		{
			if('1' == szStr[i])
			{					
				nOneBhSum++ ;
				if('0' == szStr[i+1] || '\0' == szStr[i+1])
				{					
					nMinToLeft = nOneBhSum*nZeroThisSum + FindMinStep(nOneFwSum+nOneBhSum,nZeroThisSum,i+1) ;	//继续向左决策
					nMinToRight = nOneFwSum*nZeroThisSum + FindMinStep(nOneFwSum+nOneBhSum,0,i+1) ;				//继续向右决策
					
					nMinStep = nMinToLeft < nMinToRight ? nMinToLeft : nMinToRight ;

					return nMinStep ;			//回溯
				}			
			}
			else if('0' == szStr[i])
			{			
				nZeroThisSum++ ;
			}
			i++ ;
		}	
	}	
	return nMinStep ;	//回溯
}

－－－－－－－－－－－－－－－－－－－－－－－分割线－－－－－－－－－－－－－－－－－－－－－

#include<stdio.h>
#include<memory.h>

char szStr[100005] ;
int nOneGroup[55000] ;		//记录连续1字串各有多少个1
int nZeroGroup[55000] ;		//记录1字串之前0字串有多少个0

int main(void)
{
	int i = 0 ;
	int k = 0 ;
	int j = 1 ;
	int fFindOne = 0 ;
	int nZeroIndex = -1 ;  
	int nOneIndex = 0 ; 
	int nMinStep = 0 ;
	int nTempStep = 0 ;
	int nTempZero = 0 ;

	freopen("in.txt","r",stdin) ;
	while(scanf("%s",szStr) != EOF)
	{
		i = k = 0 ;
		nZeroIndex = -1 ;
		nOneIndex = 0 ; 
		fFindOne = 0 ;
		nMinStep = nTempStep = nTempZero = 0 ;

		memset(nOneGroup,0,sizeof(nOneGroup)) ;
		memset(nZeroGroup,0,sizeof(nZeroGroup)) ;
		
		while(szStr[i] != '\0')
		{
			if('1' == szStr[i])
			{
				if(0 == fFindOne)
				{
					fFindOne = 1 ;
					nZeroIndex++ ;
				}
				nOneGroup[nOneIndex]++ ;
			}
			else if(1 == fFindOne)
			{
				nZeroGroup[nZeroIndex]++ ;			
				if('1' == szStr[i+1])
				{
					fFindOne = 0 ;
					nOneIndex++ ;
				}
			}
			i++ ;
		}

		for(i = 0 ; i <= nOneIndex ; ++i)
		{
			nTempStep = 0 ;
			nTempZero = 0 ;
			for(k = i ; k > 0 ; --k)						//左边的1字串向固定1字串移动
			{
				nTempZero += nZeroGroup[k-1] ;
				nTempStep += nOneGroup[k-1]*nTempZero ;		
			}

			nTempZero = 0 ;
			for(k = i ; k < nOneIndex ; ++k)				//右边的1字串向固定1字串移动
			{
				nTempZero += nZeroGroup[k] ;	
				nTempStep += nOneGroup[k+1]*nTempZero  ;
			}

			if(0 == i)
			{
				nMinStep = nTempStep ;
			}
			else if(nTempStep < nMinStep)
			{
				nMinStep = nTempStep ;
			}
		}	
		printf("Case #%d: %d\n",j,nMinStep) ;
		j++ ;
	}
	return 0 ;
}

#include<stdio.h>

char szStr[100005] ;		//搞错了，原来是要10万个....
int nOneGroup[55000] ;
int nZeroGroup[55000] ;		

int main(void)
{
	long i = 0 ;
	long k = 0 ;
	long j = 1 ;
	long fFindOne = 0 ;
	long nZeroIndex = -1 ;  
	long nOneIndex = 0 ; 
	long nMinStep = 0 ;
	long nTempStep = 0 ;
	long nTempZero = 0 ;

	while(scanf("%s",szStr) != EOF)
	{
		i = k = 0 ;
		nZeroIndex = -1 ;
		nOneIndex = 0 ; 
		fFindOne = 0 ;
		nMinStep = nTempStep = nTempZero = 0 ;
		
		while(szStr[i] != '\0')
		{
			if('1' == szStr[i])
			{
				if(0 == fFindOne)
				{
					fFindOne = 1 ;
					nZeroIndex++ ;
				}
				nOneGroup[nOneIndex]++ ;
			}
			else if(1 == fFindOne)
			{
				nZeroGroup[nZeroIndex]++ ;			
				if('1' == szStr[i+1])
				{
					fFindOne = 0 ;
					nOneIndex++ ;
				}
			}
			i++ ;
		}

		for(i = 0 ; i <= nOneIndex ; ++i)
		{
			nTempStep = 0 ;
			nTempZero = 0 ;
			for(k = i ; k > 0 ; --k)
			{
				nTempZero += nZeroGroup[k-1] ;
				nTempStep += nOneGroup[k-1]*nTempZero ;

				if(i == nOneIndex)
				{
					nZeroGroup[k-1] = nOneGroup[k-1] = 0 ;
				}
			}

			nTempZero = 0 ;
			for(k = i ; k < nOneIndex ; ++k)
			{
				nTempZero += nZeroGroup[k] ;	
				nTempStep += nOneGroup[k+1]*nTempZero  ;
			}

			if(0 == i)
			{
				nMinStep = nTempStep ;
			}
			else if(nTempStep < nMinStep)
			{
				nMinStep = nTempStep ;
			}

			if(i == nOneIndex)
			{
				nOneGroup[nOneIndex] = 0 ;
				nZeroGroup[nOneIndex]= 0 ;
			}
		}	
		printf("Case #%d: %d\n",j,nMinStep) ;
		j++ ;
	}
	return 0 ;
}

－－－－－－－－－－－－－－－－－－－分割线－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

#include<stdio.h>
#include<memory.h>

char szStr[100005] ;	
int nOneGroup[55000] ;
int nZeroGroup[55000] ;		

int main(void)
{
	long i = 0 ;
	long k = 0 ;
	long j = 1 ;
	long fFindOne = 0 ;
	long nZeroIndex = -1 ;  
	long nOneIndex = 0 ; 
	long nMinStep = 0 ;
	long nTempStep = 0 ;
	long nTempZero = 0 ;
	
	long fCal = 0 ;
	long nAllToLeftStep = 0 ;
	long nRightOneSum = 0 ;
	long nLeftZeroSum = 0 ;
	long nLeftOneSum = 0 ;
	long nDecreStep = 0 ;
	long nIncreStep = 0 ;
	
	while(scanf("%s",szStr) != EOF)
	{
		i = k = 0 ;
		nZeroIndex = -1 ;
		nOneIndex = 0 ; 
		fFindOne = fCal = 0 ;
		nMinStep = nTempStep = nTempZero = nAllToLeftStep = nRightOneSum = 0 ;	
		nLeftZeroSum = nLeftOneSum = nDecreStep = nIncreStep = 0 ;
				
		memset(nOneGroup,0,sizeof(nOneGroup)) ;
		memset(nZeroGroup,0,sizeof(nZeroGroup)) ;
		
		while(szStr[i] != '\0')
		{
			if('1' == szStr[i])
			{
				if(0 == fFindOne)
				{
					fFindOne = 1 ;
					nZeroIndex++ ;
				}
				if('0' == szStr[i+1] || '\0' == szStr[i+1])
				{
					fCal = 1 ;
				}
				nOneGroup[nOneIndex]++ ;
				
				if(nOneIndex >= 1 && 1 == fCal)
				{
					nTempZero += nZeroGroup[nOneIndex-1] ;
					nTempStep += nTempZero*nOneGroup[nOneIndex] ;
					nRightOneSum += nOneGroup[nOneIndex] ;
				}
				fCal = 0 ;
			}
			else if(1 == fFindOne)
			{
				nZeroGroup[nZeroIndex]++ ;			
				if('1' == szStr[i+1])
				{
					fFindOne = 0 ;
					nOneIndex++ ;
				}
			}		
			i++ ;
		}
		
		nMinStep = nTempStep ;
		nAllToLeftStep = nTempStep ;
		
		for(i = 1 ; i <= nOneIndex ; ++i)
		{
			nTempStep = 0 ;
			nLeftZeroSum = nZeroGroup[i-1] ;
			nDecreStep += nRightOneSum * nLeftZeroSum ;
			nLeftOneSum += nOneGroup[i-1] ;
			nIncreStep += nLeftOneSum * nZeroGroup[i-1] ;
			
			nTempStep = nAllToLeftStep - nDecreStep + nIncreStep ;
			nRightOneSum -= nOneGroup[i] ; 
			
			if(nTempStep < nMinStep)
			{
				nMinStep = nTempStep ;
			}		
		}	
		printf("Case #%d: %d\n",j,nMinStep) ;
		j++ ;
	}
	return 0 ;
}

#include<stdio.h>

char szStr[100005] ;	
int nOneGroup[55000] ;
int nZeroGroup[55000] ;		

int main(void)
{
	long i = 0 ;
	long k = 0 ;
	long j = 1 ;
	long fFindOne = 0 ;
	long nZeroIndex = -1 ;  
	long nOneIndex = 0 ; 
	long nMinStep = 0 ;
	long nTempStep = 0 ;
	long nTempZero = 0 ;
	
	long fCal = 0 ;
	long nAllToLeftStep = 0 ;
	long nRightOneSum = 0 ;
	long nLeftZeroSum = 0 ;
	long nLeftOneSum = 0 ;
	long nDecreStep = 0 ;
	long nIncreStep = 0 ;
	
	while(scanf("%s",szStr) != EOF)
	{
		i = k = 0 ;
		nZeroIndex = -1 ;
		nOneIndex = 0 ; 
		fFindOne = fCal = 0 ;
		nMinStep = nTempStep = nTempZero = nAllToLeftStep = nRightOneSum = 0 ;	
		nLeftZeroSum = nLeftOneSum = nDecreStep = nIncreStep = 0 ;
						
		while(szStr[i] != '\0')
		{
			if('1' == szStr[i])
			{
				if(0 == fFindOne)
				{
					fFindOne = 1 ;
					nZeroIndex++ ;
				}
				if('0' == szStr[i+1] || '\0' == szStr[i+1])
				{
					fCal = 1 ;
				}
				nOneGroup[nOneIndex]++ ;
				
				if(nOneIndex >= 1 && 1 == fCal)
				{
					nTempZero += nZeroGroup[nOneIndex-1] ;
					nTempStep += nTempZero*nOneGroup[nOneIndex] ;
					nRightOneSum += nOneGroup[nOneIndex] ;
				}
				fCal = 0 ;
			}
			else if(1 == fFindOne)
			{
				nZeroGroup[nZeroIndex]++ ;			
				if('1' == szStr[i+1])
				{
					fFindOne = 0 ;
					nOneIndex++ ;
				}
			}		
			i++ ;
		}
		
		nMinStep = nTempStep ;
		nAllToLeftStep = nTempStep ;
		
		for(i = 1 ; i <= nOneIndex ; ++i)
		{
			nTempStep = 0 ;
			nLeftZeroSum = nZeroGroup[i-1] ;
			nDecreStep += nRightOneSum * nLeftZeroSum ;
			nLeftOneSum += nOneGroup[i-1] ;
			nIncreStep += nLeftOneSum * nZeroGroup[i-1] ;
			
			nTempStep = nAllToLeftStep - nDecreStep + nIncreStep ;
			nRightOneSum -= nOneGroup[i] ; 
			
			if(nTempStep < nMinStep)
			{
				nMinStep = nTempStep ;
			}	
			
			nZeroGroup[i-1] = nOneGroup[i-1] = 0 ;
			if(nOneIndex == i)
			{
				nOneGroup[i] = 0 ;
				nZeroGroup[i-1] = nZeroGroup[i] = 0 ;
			}
		}
		if(0 == nOneIndex)
		{
			nZeroGroup[0] = nOneGroup[0] = 0 ;
		}
		printf("Case #%d: %d\n",j,nMinStep) ;
		j++ ;
	}
	return 0 ;
}

－－－－－－－－－－－－－－－－－－－分割线－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

/* －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

最后就是想问一下一开始想到的动态规划法。

不知道对于这一道题来说，动态规划法是否可行？动态规划的可行条件为：最优子结构和无后效性，这两个

我都没有找到但是又觉得动态规划可行。因为上一种回溯法中已经涉及到动态决策问题，而动态规划可以用

在这些地方，这里的向左向右合并就涉及到了决策的问题。

动态规划法的核心是状态和状态转移方程，对于这一道题来说，状态应该是此时左边字串连续1的个数，而状

太转移方程应该就是向左向右移动产生的代价等等的方程(好吧，我不会写 = =)...

所以求指教.................

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

－－－－－－－－－－－－－－－－－－－分割线－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

附icelights同学的解法，一种完全不同的思路，很不错：http://blog.csdn.net/icelights/article/details/7713058

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

ACM-Position Arrangement (解题报告)

Description:

Input:

Output:

Sample Input:

Sample Output:

Source:

继续阅读

DateTimePicker 控件的格式设置

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

C++数组引用C++数组引用

笔试面试题目：滑动窗口(二)

PAT 1089 Insert or Merge[难]

数据结构与算法（27）——排序（二）

[C++学习历程]基础部分 C++中的函数学习

Dijkstra--简易版（最短路径）

Git学习笔记5 merge冲突时二选一

使用递减运算符在循环中按递减顺序打印10到0之间的整数

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

指针，常量和类型别名

VS C++常见问题集锦1.在Vs中编C出现这两个错误是什么原因？错误1：error LNK2005: _main 已经在 *** 中定义

hdu7108哈希