首页 > ACM题库 > HDU-杭电 > HDU 3777-Page Count[解题报告]HOJ
2015
04-10

HDU 3777-Page Count[解题报告]HOJ

Page Count

问题描述 :

When you execute a word processor’s print command, you are normally prompted to specify the pages you want printed. You might, for example, enter:

10-15,25-28,8-4,13-20,9,8-8
The expression you enter is a list of print ranges, separated by commas.

Each print range is either a single positive integer, or two positive integers separated by a hyphen. In the latter case we call the first integer low and the second one high. A print range for which low > high is simply ignored. A print range that specifies page numbers exceeding the number of pages is processed so that only the pages available in the document are printed. Pages are numbered starting from 1.

Some of the print ranges may overlap. Pages which are common to two or more print ranges will be printed only once. (In the example given, pages 13, 14 and 15 are common to two print ranges.)

输入:

The input will contain data for a number of problem instances. For each problem instance there will be two lines of input. The first line will contain a single positive integer: the number of pages in the document. The second line will contain a list of print ranges, as defined by the rules stated above. End of input will be indicated by 0 for the number of pages. The number of pages in any book is at most 1000. The list of print ranges will be not be longer than 1000 characters.

输出:

The input will contain data for a number of problem instances. For each problem instance there will be two lines of input. The first line will contain a single positive integer: the number of pages in the document. The second line will contain a list of print ranges, as defined by the rules stated above. End of input will be indicated by 0 for the number of pages. The number of pages in any book is at most 1000. The list of print ranges will be not be longer than 1000 characters.

样例输入:

30
10-15,25-28,8-4,13-20,9,8-8
19
10-15,25-28,8-4,13-20,9,8-8
0

样例输出:

17
12

//============================================================================
// Name : E.cpp
// Author : 
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>


using namespace std;


int N;

bool vis[1100];

char str[1100];

int main()
{
//	freopen("input.txt","r",stdin);
	setbuf(stdout,NULL);
	int s,t;
	while(scanf("%d",&N)!=EOF && N)
	{
		for(int i=1;i<=N;i++)
			vis[i]=false;
		scanf("%s",str);
		char * p;
		p=strtok(str,",");
		while(p)
		{
//			sscanf(p,"%d-%d",&s,&t);
			bool bingo=false;
			for(char* x=p;*x;x++)
				if('-'==*x)
				{
					bingo=true;
					break;
				}
			if(bingo)
			{
				sscanf(p,"%d-%d",&s,&t);
//				printf("%d %d\n",s,t);
				if(s<=t)
				{
					for(int i=s;i<=t;i++)
					{
						if(i<=0 || i>N)
							break;
						vis[i]=true;
					}
				}
			}
			else
			{
				sscanf(p,"%d",&s);
				if(s>=1 && s<=N)
					vis[s]=true;
			}

//			printf("%d %d\n",s,t);

			p=strtok(NULL,",");
		}
		int res=0;
		for(int i=1;i<=N;i++)
		{
			if(vis[i])
				res++;
		}
		printf("%d\n",res);
	}











	return 0;
}

  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. [email protected]