POJ 题目1250 Tanning Salon (链表应用)


Tanning Salon
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 6820   Accepted: 3686

Description

Tan Your Hide, Inc., owns several coin-operated tanning salons. Research has shown that if a customer arrives and there are no beds available, the customer will turn around and leave, thus costing the company a sale. Your task is to write a program that tells the company how many customers left without tanning. 

Input

The input consists of data for one or more salons, followed by a line containing the number 0 that signals the end of the input. Data for each salon is a single line containing a positive integer, representing the number of tanning beds in the salon, followed by a space, followed by a sequence of uppercase letters. Letters in the sequence occur in pairs. The first occurrence indicates the arrival of a customer, the second indicates the departure of that same customer. No letter will occur in more than one pair. Customers who leave without tanning always depart before customers who are currently tanning. There are at most 20 beds per salon. 

Output

For each salon, output a sentence telling how many customers, if any, walked away. Use the exact format shown below. 

Sample Input

2 ABBAJJKZKZ
3 GACCBDDBAGEE
3 GACCBGDDBAEE
1 ABCBCA
0

Sample Output

All customers tanned successfully.
1 customer(s) walked away.
All customers tanned successfully.
2 customer(s) walked away.






建立两个链表L,W,  L用来存放当前bed状态,W用来存放当前wait等待人数,

每当新到达一个新的客户,

首先判断新客户是否已在L中,如果在L中,将其从L删除,

如果不在L,再判断元素个数是否大于n,

如果L中元素个数小于n,则将新客户添加到L,

否则,判断新客户是否在W中,如果不在,则cnt++(等待人数++);如果在w中,则从w删除





#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

typedef struct node
{
	char elem;
	node * next;
}node;
typedef struct list
{
	node * head;
}list;
	
void Print(list L)
{
	node *p=L.head;
	while(p)
	{
		printf("%c",p->elem);
		p=p->next;
	}
//	printf("-----------\n");
}
int length(list L)
{
	node * p = L.head;
	int len = 0;
	while(p)
	{
		len++;
		p = p->next;
	} 
	return len;
	
}
void insert(list &L, char e)
{
	node * p;
	p = (node *)malloc(sizeof(node));
	p->elem = e;	
	p->next = L.head;
	L.head = p;	
	//Print(L);
}
void delet(list &L, char e)
{
	node * c;
//	Print(L);
	node * p = L.head;
	node * s=p;
	if(p->elem ==e)
	{
		L.head = p->next;
	}
	else
	{
		while( p->elem != e)
		{
			s = p;
			p = p->next;
		} 
		s->next = p->next;
	}
	
	free(p);
	
}
bool find(list L, char e)
{
	node * p = L.head; 
	while(p)
	{
		if( p->elem==e) 	return true;
		p=p->next;
	}
//	printf("meiyou\n");
	return false;
}

void init(list &L)
{
	L.head = (node *)malloc(sizeof(node));
	if(!L.head) exit(-1);
	L.head=NULL;
}

int main()
{
	int n,i;
	char s[1000];
	list L;
	list W;
	init(L); init(W);
	while(scanf("%d",&n),n)
	{
		scanf("%s",s);
	//	puts(s);
	//	printf("n=%d\n",n);
//   3 GACCBDDBAGEE
	
	//	printf("l=%c,len=%d\n",s[0],strlen(s));

	//	Print(L);
		int cnt = 0;

		for(i=0;i<strlen(s);i++)
		{
		//	printf("i=%c,len=%d\n",s[i],length(L));
			if(!find(L,s[i]))//对L来说新来客户
			{
				if(length(L)<n ){
					insert(L,s[i]);
			//		Print(L);
				 }
				else
				{	
				//	printf("###\n");
				//	Print(W);

					if(!find(W,s[i]))	
					{
						
						insert(W,s[i]);
						cnt ++;
					}
					else delet(W,s[i]);
				} 
				//Print(L);
			}
			else delet(L,s[i]);
			
		}
		if(cnt==0) printf("All customers tanned successfully.\n");
		else printf("%d customer(s) walked away.\n",cnt);
		
	}
	return 0;
}


链表——约瑟夫问题 百练2746

约瑟夫问题


建立循环链表,一次删除符合结点,最后剩下一个即为所求结点

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

struct node 
{
	int num;
	node * next;
};

void initqueen(int n,node * queen)
{
	int i;
	node * r,*s;
	r=s=queen;

	for(i=2;i<=n;i++)//2到n结点
	{
		
		s = (node *)malloc(sizeof(node));
		s->num = i;
		s->next = NULL;
		r->next = s;
		r = s;
	}
//	printf("r=%d\n",r->num);
	r->next = queen;//最后一个结点指向头结点,形成循环队列
}
int solve(int n,int m,node * queen)
{
	int i,j;
	node * s;
	node *p = queen;
//	printf("q = %d\n",queen->num);

	s = p;
	for(i=1;i<n;i++)
	{
		
	//	printf("p=%d\n",p->num);
		for(j=1;j<m;j++)
		{
			
			s = p;
			p=p->next;
		//	s = p;
		}
	//	printf("*p=%d\n",p->num);
		s->next = p->next;
		free(p);
		p = s->next;
	}
	return p->num;
}
int main()
{
 	int m,n;
	node * queen;
 	while(scanf("%d%d",&n,&m),m&&n)
 	{ 
	//	printf("n=%d,m=%d\n",n,m);
		
	 	if(n==1) {
			printf("1\n");	continue;
	 	}
		if(m==1){
			printf("%d\n",n); continue;
		}
		queen = (node *)malloc(sizeof(node)); //第一个结点
		queen->num = 1;
		queen->next = NULL;;
		 initqueen(n,queen);
		 printf("%d\n",solve(n,m,queen));					   								
	}
 	return 0;
}


最短路径 Dijksstra算法求最短路

1.两地之间是否有通路?
2.若存在多条通路,哪条路最短?

    

单源最短路径
   Single-Source Shortest Path
                                 (Dijkstra算法)
   负权边的有向图单源最短有路径
    Bellman-Ford算法

 

所有顶点对间的最短路径问题
   All-Pairs Shortest paths        Floyd算法)
问题: 带权有向图G(E,V), 找出从给定源顶点s其它顶点v的权最小路径。
“最短路径” = 最小权

 

 在日常生活中,我们如果需要常常往返A地区和B地区之间,我们最希望知道的可能是从A地区到B地区间的众多路径中,那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。确定起点的最短路径问题:即已知起始结点,求最短路径的问题。

 Dijkstra算法

  Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。

如下图:

 

贪心算法:
  基于以下原理:若顶点序列{Vs,V1,…,Vn} 是从Vs到Vn的最短路,则序列 {Vs,V1,…,Vn-1} 必为从Vs到Vn-1的最短路。
基本思想:
   设置一个顶点集S,不断做贪心选择扩充这个集合。
  一个顶点属于S当且仅当从源到该顶点最短路径长度已知。
 
 
图中从v0到其余各顶点之间的最短路径:
v0      v1    
v0     v2   (v0,v2)               10
 v0    v3   (v0,v4,v3)          50
 v0    v4   (v0,v4)                30
 v0    v5   (v0,v4,v3,v5)     60
 
  初始时,S仅包含源s,
 特殊路径:
  从源到G中某一顶点u且中间只经过S中顶点的路称为从源到u的特殊路径
 算法每次从V-S中取出具有最短特殊路径
   长度的顶点u加入S中。
算法思想:
   按路径长度递增序产生各顶点最短路径
 
 
 
用到的变量:
 
int  G[maxnum][maxnum]; //邻接矩阵,距离无限远用9999表示
 
int  dist[maxnum]; //存放各个顶点到源点的寻短路径;
 
bool  visit[maxnum] ;  //标志该定点是否被访问,初始化wei 0
 
int last;//表示当前所走路径最后一个节点
 
利用贪心算法,首先从原点出发,初始化dist[maxnum]; 假如源点v0,顶点数目6  (v0,v1,v2,v3,v4,v5);
 
for i=0 to 5 ,dist[i]=G[0][i];   
 然后dist[0] = 0;//到本身距离为0, 再标记V0点, visit[0] = 1;//以访问v0点,
此时dist[5]={0,9999,30,9999,30,100};  visit[]={1,0,0,0,0,0};  last = 0;//v0点为当前路径最后一个
 
然后for循环,寻找从源点到其他店的最小距离,并且该点未被访问,
 
int min = 9999;
for(j=0;j<n;j++) 
{
    if(!visit[j] && min< G[v0][j])
   {
         min = G[last][j];
                    last = j;
   }
}

 
得到 last=2;//将v2加入当前路径 ,    visit[last] = 1; 
visit[] = {1,0,1,0,0,0}
 
然后将dist[]数组更新。, 更新为V0到各个点的最短路径
然后循环,直到所有结点都被访问;
 
for(j=0;j<n;j++)
 { 
         if(!visit[j] && G[last][j]!=99999)
          { 
                   int newdist = dist[last] + G[last][j];
                   if(newdist < dist[j])
                        { 
                                dist[j] = newdist;
                                     prev[j] = last;
                         } 
            } 
 }
 

 
 
 
 
 
练习:  Hdu 2544   hdu1874
 
#include <iostream>

using namespace std;

void Dijkstra(int n,int v,int *dist,int *prev,int G[102][102]) 
{
    bool visit[102];//存放顶点是否被访问
    int i,j;
    for(i=1; i<=n; i++)
    {
        visit[i] = 0;
        dist[i] = G[v][i];
        if(dist[i]== 99999) prev[i] = 0;
        else prev[i] = v;    
    } 
    
    dist[v] = 0; 
    visit[v] = 1;
    
     for(i=2;i<=n;i++)//访问剩下的点
     {
        int last = v;
        int min = 99999; 
        //寻找本行未使用点j的dist[j]最小值
        for(j=1;j<=n;j++)
        {
            if(!visit[j]&& min>dist[j])    
            {
                
                min = dist[j];
                last = j;//距离最小点的号码 
            }
        }    
        
        visit[last] = 1;//访问该距离最小点
        
        //将dist[]刷新
        for(j=1;j<=n;j++)
        {
            if(!visit[j] && G[last][j]!=99999)
            {
                int newdist = dist[last] + G[last][j];
                
                if(newdist < dist[j])
                {
                    dist[j] = newdist;
                    prev[j] = last;    
                }
            }
    //        printf("%d ",dist[j]);    
        }    
    //    printf("\n");
    } 
}


int main()
{

    int i,j,a,b,c;
    int dist[102];  
    int prev[102];  //记录当前点的前一个结点
    int G[102][102];
    int vnum,m; 
    
    while(scanf("%d%d",&vnum,&m),m&&vnum)
    {    
        
        for(i=1;i<=vnum;i++)
            for(j=1;j<=vnum;j++)
                G[i][j] = 99999;
    
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            G[a][b] = G[b][a] = c;    
        }
        
        for(i=1;i<=vnum;i++)
            dist[i] = 99999; //原点到各个点距离初始化
        
    //    for(i=1;i<=vnum;i++) //输出创建的邻接矩阵 
//        {
//            for(j=1;j<=vnum;j++)
//                printf("%4d",G[i][j]);
//            printf("\n");
//        } 

        Dijkstra(vnum,1,dist,prev,G);
        printf("%d\n",dist[vnum]);
    
    }
    
    return 0;    
}

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

中缀式转后缀表达式 -NYOJ 题目267郁闷的C小加(二)

郁闷的C小加(二)

时间限制:1000 ms  |  内存限制:65535 KB
难度:4
描述

聪明的你帮助C小加解决了中缀表达式到后缀表达式的转换(详情请参考“郁闷的C小加(一)”),C小加很高兴。但C小加是个爱思考的人,他又想通过这种方法计算一个表达式的值。即先把表达式转换为后缀表达式,再求值。这时又要考虑操作数是小数和多位数的情况。

输入
第一行输入一个整数T,共有T组测试数据(T<10)。
每组测试数据只有一行,是一个长度不超过1000的字符串,表示这个运算式,每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数并且小于1000000。
数据保证除数不会为0。
输出
对于每组测试数据输出结果包括两行,先输出转换后的后缀表达式,再输出计算结果,结果保留两位小数。两组测试数据之间用一个空行隔开。
样例输入
21+2=
(19+21)*3-4/5=
样例输出
12+=
3.00
 
1921+3*45/-=
119.20

本题用到的技巧:

1.#include<stack> 其中第一好了栈以及其操作,简化了代码

2.atof函数

功 能: 把字符串转换成浮点数
表头文件 #include <stdlib.h>
名字来源:ascii to floating point numbers 的缩写
用 法: double atof(const char *nptr);
程序例:
#include <stdlib.h> 
#include <stdio.h> 
int main() 
{   
	float f;   
 	char *str = "12345.67";   
	f = atof(str);   
	printf("string = %s float = %f\n", str, f);   
	return 0; 
} 


相关函数 atoiatolstrtodstrtolstrtoul

3.sscanf函数 提取一个字符串中的各个类型的数据,分类提取很方便

 

WA了数十次,一开始我以为是情况没考虑完,停了几天后忽然想到是不是后缀表达式煤球正确

然后找了 中缀表达式转后缀的方法:

1)规则

中缀表达式a + b*c + (d * e + f) * g,其转换成后缀表达式则为a b c * + d e * f  + g * +。

转换过程需要用到栈,具体过程如下:

1)如果遇到操作数,我们就直接将其输出。

2)如果遇到操作符,则我们将其放入到栈中,遇到左括号时我们也将其放入栈中。

3)如果遇到一个右括号,则将栈元素弹出,将弹出的操作符输出直到遇到左括号为止。注意,左括号只弹出并不输出。

4)如果遇到任何其他的操作符,如(“+”, “*”,“(”)等,从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后,才将遇到的操作符压入到栈中。有一点需要注意,只有在遇到" ) "的情况下我们才弹出" ( ",其他情况我们都不会弹出" ( "。也就是说这种操作," + "的优先级最低," ( "优先级最高。

5)如果我们读到了输入的末尾,则将栈中所有元素依次弹出。

 

2)实例

规则很多,还是用实例比较容易说清楚整个过程。以上面的转换为例,输入为a + b * c + (d * e + f)*g,处理过程如下:

1)首先读到a,直接输出。

2)读到“+”,将其放入到栈中。

3)读到b,直接输出。

此时栈和输出的情况如下:

 

4)读到“*”,因为栈顶元素"+"优先级比" * " 低,所以将" * "直接压入栈中。

5)读到c,直接输出。

此时栈和输出情况如下:

 

6)读到" + ",因为栈顶元素" * "的优先级比它高,所以弹出" * "并输出, 同理,栈中下一个元素" + "优先级与读到的操作符" + "一样,所以也要弹出并输出。然后再将读到的" + "压入栈中。

此时栈和输出情况如下:

 

7)下一个读到的为"(",它优先级最高,所以直接放入到栈中。

8)读到d,将其直接输出。

此时栈和输出情况如下:

 

9)读到" * ",由于只有遇到" ) "的时候左括号"("才会弹出,所以" * "直接压入栈中。

10)读到e,直接输出。

此时栈和输出情况如下:

 

11)读到" + ",弹出" * "并输出,然后将"+"压入栈中。

12)读到f,直接输出。

此时栈和输出情况:

 

 

13)接下来读到“)”,则直接将栈中元素弹出并输出直到遇到"("为止。这里右括号前只有一个操作符"+"被弹出并输出。

 

14)读到" * ",压入栈中。读到g,直接输出。

 

15)此时输入数据已经读到末尾,栈中还有两个操作符“*”和" + ",直接弹出并输出。

至此整个转换过程完成。程序实现代码后续再补充了。

 

 3)转换的另一种方法

1)先按照运算符的优先级对中缀表达式加括号,变成( ( a+(b*c) ) + ( ((d*e)+f) *g ) )

2)将运算符移到括号的后面,变成((a(bc)*)+(((de)*f)+g)*)+

3)去掉括号,得到abc*+de*f+g*+

 

计算就好说了,根据后缀表达式,遇到运算符则弹出两个操作数,计算后压栈,最后栈顶元素为计算结果

代码:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <stack>

using namespace std;
 

int In(char e)
{
	if(e=='(' || e==')' || e=='+' || e=='-' || e=='*' || e=='/') return 1;
	else return 0;
}
int cmp(char c)
{
	switch(c)
	{
		case '+':
		case '-': return 1;
		case '*':
		case '/': return 2;
		default : return 0;	
	}	
}
double calculate(char op,double k1,double k2)
{
	double k;
	switch (op)
	{
		case '+': k = k1+k2; break;
		case '-': k = k1-k2; break;
		case '*': k = k1*k2; break;
		case '/': k = k1/k2; break;
	}
	return k;
}

/*
20
(2.6)-(1.666)=
1+2=
(19+21)*3-4/5=

*/

void change(char str[])
{
	int t,i,k,m;
	char e,buf[1002],op,s[1002];
	double kk,k1,k2;
	stack <char> S1;
	stack <double> S2;
	k=0;
	S1.push('=');
	for(i=0;i<strlen(str)-1;++i) //最后一位是 = 
	{
			if( In(str[i])  )
			{				
				switch(str[i])
				{
					case '(': S1.push(str[i]); break;
					case ')': //遇到右括号, 
						while(S1.top()!='(')//弹出栈元素输出 直到 (,
						{
							s[k++]=S1.top();
							k1 = S2.top(); S2.pop();
							k2 = S2.top(); S2.pop();
							S2.push(calculate(S1.top(),k2,k1));
							S1.pop();	
						}
						if(S1.top()=='(')//弹出(不输出
						{
							S1.pop();	
						} 

						break;
					default :
						while(cmp(str[i])<=cmp(S1.top()))
						{
							s[k++]=S1.top();
							k1 = S2.top(); S2.pop();
							k2 = S2.top(); S2.pop();
							S2.push(calculate(S1.top(),k2,k1));
							S1.pop();	
						}
						S1.push(str[i]);
						break;
				}//switch
			}//if
			else{

				sscanf(str+i,"%[^=()+*/-]",buf); //操作数 
				for(m=0;m<strlen(buf);m++) s[k++]=buf[m];
				//printf("%s",buf);
				i += strlen(buf)-1;
				kk = atof(buf);
				//printf("k = %lf\n",k);
				S2.push(kk);

			}

			
		}//for
		while(!S1.empty())
		{
			if(S1.top()!='(' && S1.top()!='=')
			{
				s[k++]=S1.top();
				k1 = S2.top(); S2.pop();
				k2 = S2.top(); S2.pop();
				S2.push(calculate(S1.top(),k2,k1));
			}
				
			S1.pop();
		}

		for(i=0;i<k;i++) printf("%c",s[i]);
		printf("=\n");
		printf("%.2lf\n",S2.top());		
} 
int main()
{
	int t,i;
	char e,str[1002],buf[1002],op;
	double k,k1,k2;
		
	scanf("%d",&t); getchar();
	while(t--)
	{
		
		gets(str); 
		//puts(str);
		change(str);
		
		if(t>0) printf("\n");
	}

	return 0;
}
/*
20
1+2=
(19+21)*3-4/5=

*/
        


注意:中缀表达式转为后缀表达式的方法。。。。。。

贪心——HDU题目1009 FatMouse' Trade

FatMouse' Trade

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 33504    Accepted Submission(s): 10897


Problem Description
FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.
 


 

Input
The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.
 


 

Output
For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.
 


 

Sample Input
5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10
1 0
0 1
1 0
-1 -1
 


 

Sample Output
13.333 31.500
0.000
1.000
 

类似于0-1背包问题

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef struct ROOM
{
    int j,f;
}ROOM;
ROOM room[10001];

bool cmp(ROOM a,ROOM b)
{
    return 1.0*a.j/a.f > 1.0*b.j/b.f;    
}
int main()
{
    int n,m,i;
    double max;
    while(scanf("%d%d",&m,&n) && (m!=-1||n!=-1))
    {
        if(n==0)//zhe里是特殊情况 
        {
            printf("0.000\n");continue;    
        }
        for(i=0;i<n;i++) 
            scanf("%d%d",&room[i].j,&room[i].f);    
        sort(room,room+n,cmp);
        //for(i=0;i<n;i++)
        //    printf("%d %d\n",room[i].j,room[i].f);
        max = i = 0;
        if(m==0)//第一次提交没考虑特殊情况
        {
            if(room[i].f==0)
            {
                max+=room[i].j;    
            }    
            i++;
        }
        while(m)
        {
            if(m>=room[i].f)
            {
                max += room[i].j;    
                m -= room[i].f;
            }
            else
            {
                max += 1.0 * room[i].j/room[i].f *m;    
                m=0;    
            }
            i++;
        }
        printf("%.3lf\n",max);
    }
    return 0;
}


 

贪心——NYOJ 题目236 心急的C小加

心急的C小加

时间限制:1000 ms  |  内存限制:65535 KB
难度:4
描述

C小加有一些木棒,它们的长度和质量都已经知道,需要一个机器处理这些木棒,机器开启的时候需要耗费一个单位的时间,如果第i+1个木棒的重量和长度都大于等于第i个处理的木棒,那么将不会耗费时间,否则需要消耗一个单位的时间。因为急着去约会,C小加想在最短的时间内把木棒处理完,你能告诉他应该怎样做吗?

输入
第一行是一个整数T(1<T<1500),表示输入数据一共有T组。
每组测试数据的第一行是一个整数N(1<=N<=5000),表示有N个木棒。接下来的一行分别输入N个木棒的L,W(0 < L ,W <= 10000),用一个空格隔开,分别表示木棒的长度和质量。
输出
处理这些木棒的最短时间。
样例输入
3 
5 
4 9 5 2 2 1 3 5 1 4 
3 
2 2 1 1 2 2 
3 
1 3 2 2 3 1 
样例输出
2
1
3

分析:只要将长度重量排序,找出其中的递增子序列个数即可,

先按长度排序,(长度相等,按重量) 然后看排好序的 数组中 ,只看重量的递增子序列即可(长度已排好序)

重点求递增子序列个数, 求一个数组中递增子序列个数,可以在附加设置一个标志数组flag[],用来标记对应的元素

如 a[8]={2,3,5,4,6,8,7};

从i=0开始比当前元素大的即与当前元素属于同一个子序列,将当前元素加入到子序列中,并且标记为已读,再继续判读下一个元素是否大于已有子序列最后(最大)一个元素,判断完即可

[code]

 

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

using namespace std;

typedef struct Stick
{
	int L,W;
}Stick;

Stick stick [5001];
bool flag[5001];//标记数组,定义成bool可节省内存,也可减少判断时间

bool cmp(Stick  a,Stick b)//先按长度排序,长度相等按重量排序 
{
	if(a.L==b.L)	return  a.W<b.W ;
	else return a.L<b.L;	
}

int main()
{
	int t,s,n,m,i,j,cnt;
	int value,weight;
    scanf("%d",&t);
    while(t--)
    {
			memset(flag,0,sizeof(flag)); 
            scanf("%d",&n);
            for(i=0;i<n;i++)     scanf("%d%d",&stick[i].L,&stick[i].W); 
            sort(stick,stick+n,cmp);
			
			//for(i=0;i<n;i++) printf("L=%d W=%d\n",stick[i].L,stick[i].W);
			
			cnt = 0;
			for(i=0;i<n;i++) 
			{
			//	printf("flag=%d\n",flag[i]);
				if(!flag[i])
				{
					//printf("**\n");
					cnt++;
					int last = stick[i].W;//设置子序列为第一个元素 
					for(j=i+1;j<n;j++)
					{
						if(last<=stick[j].W && !flag[j])//因为是求递增子序列故 stick[j].w 必须大于子序列最后一个元素 
						{
							flag[j]=1;//标记j位置变为已处理木棍	
							last = stick[j].W;//记录递增子序列的最后一个元素 ,将stick[j]添加进来 
						}	
					}	
				}
			}
 
			printf("%d\n",cnt);    
    }
   //system("pause");
 return 0;    
}        


 

STL中sort函数的用法

0 前言: STL,为什么你必须掌握

 

stable_sort(array,array+n,cmp);

sort(array,array+n,cmp);

cmp函数的书写,

对于结构体

bool cmp(STRUCT a, STRUCT b)//STRUCT为结构体leixing名

{

       return a.aa>b.aa;//这里写条件

}


对于程序员来说,数据结构是必修的一门课。从查找到排序,从链表到二叉树,几乎所有的算法和原理都需要理解,理解不了也要死记硬背下来。幸运的是这些理论都已经比较成熟,算法也基本固定下来,不需要你再去花费心思去考虑其算法原理,也不用再去验证其准确性。不过,等你开始应用计算机语言来工作的时候,你会发现,面对不同的需求你需要一次又一次去用代码重复实现这些已经成熟的算法,而且会一次又一次陷入一些由于自己疏忽而产生的bug中。这时,你想找一种工具,已经帮你实现这些功能,你想怎么用就怎么用,同时不影响性能。你需要的就是STL, 标准模板库!

西方有句谚语:不要重复发明轮子!

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会发现你已不用拘泥于算法本身,从而站在巨人的肩膀上去考虑更高级的应用。

排序是最广泛的算法之一,本文详细介绍了STL中不同排序算法的用法和区别。

1 STL提供的Sort 算法


C++之所以得到这么多人的喜欢,是因为它既具有面向对象的概念,又保持了C语言高效的特点。STL 排序算法同样需要保持高效。因此,对于不同的需求,STL提供的不同的函数,不同的函数,实现的算法又不尽相同。

1.1 所有sort算法介绍

所有的sort算法的参数都需要输入一个范围,[begin, end)。这里使用的迭代器(iterator)都需是随机迭代器(RadomAccessIterator), 也就是说可以随机访问的迭代器,如:it+n什么的。(partition 和stable_partition 除外)

如果你需要自己定义比较函数,你可以把你定义好的仿函数(functor)作为参数传入。每种算法都支持传入比较函数。以下是所有STL sort算法函数的名字列表:

函数名 功能描述
sort 对给定区间所有元素进行排序
stable_sort 对给定区间所有元素进行稳定排序
partial_sort 对给定区间所有元素部分排序
partial_sort_copy 对给定区间复制并排序
nth_element 找出给定区间的某个位置对应的元素
is_sorted 判断一个区间是否已经排好序
partition 使得符合某个条件的元素放在前面
stable_partition 相对稳定的使得符合某个条件的元素放在前面
其中nth_element 是最不易理解的,实际上,这个函数是用来找出第几个。例如:找出包含7个元素的数组中排在中间那个数的值,此时,我可能不关心前面,也不关心后面,我只关心排在第四位的元素值是多少。

1.2 sort 中的比较函数

当你需要按照某种特定方式进行排序时,你需要给sort指定比较函数,否则程序会自动提供给你一个比较函数。
vector < int > vect;
//...
sort(vect.begin(), vect.end());
//此时相当于调用
sort(vect.begin(), vect.end(), less<int>() );

上述例子中系统自己为sort提供了less仿函数。在STL中还提供了其他仿函数,以下是仿函数列表:
名称 功能描述
equal_to 相等
not_equal_to 不相等
less 小于
greater 大于
less_equal 小于等于
greater_equal 大于等于
需要注意的是,这些函数不是都能适用于你的sort算法,如何选择,决定于你的应用。另外,不能直接写入仿函数的名字,而是要写其重载的()函数:
less<int>()
greater<int>()
当你的容器中元素时一些标准类型(int float char)或者string时,你可以直接使用这些函数模板。但如果你时自己定义的类型或者你需要按照其他方式排序,你可以有两种方法来达到效果:一种是自己写比较函数。另一种是重载类型的'<'操作赋。
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;

class myclass {
        public:
        myclass(int a, int b):first(a), second(b){}
        int first;
        int second;
        bool operator < (const myclass &m)const {
                return first < m.first;
        }
};

bool less_second(const myclass & m1, const myclass & m2) {
        return m1.second < m2.second;
}

int main() {

        vector< myclass > vect;
        for(int i = 0 ; i < 10 ; i ++){
                myclass my(10-i, i*3);
                vect.push_back(my);
        }
        for(int i = 0 ; i < vect.size(); i ++)
        cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
        sort(vect.begin(), vect.end());
        cout<<"after sorted by first:"<<endl;
        for(int i = 0 ; i < vect.size(); i ++)
        cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
        cout<<"after sorted by second:"<<endl;
        sort(vect.begin(), vect.end(), less_second);
        for(int i = 0 ; i < vect.size(); i ++)
        cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";

        return 0 ;
}

知道其输出结果是什么了吧:
(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)
after sorted by first:
(1,27)
(2,24)
(3,21)
(4,18)
(5,15)
(6,12)
(7,9)
(8,6)
(9,3)
(10,0)
after sorted by second:
(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)

1.3 sort 的稳定性

你发现有sort和stable_sort,还有 partition 和stable_partition, 感到奇怪吧。其中的区别是,带有stable的函数可保证相等元素的原本相对次序在排序后保持不变。或许你会问,既然相等,你还管他相对位置呢,也分不清楚谁是谁了?这里需要弄清楚一个问题,这里的相等,是指你提供的函数表示两个元素相等,并不一定是一摸一样的元素。

例如,如果你写一个比较函数:

bool less_len(const string &str1, const string &str2)
{
        return str1.length() < str2.length();
}

此时,"apple" 和 "winter" 就是相等的,如果在"apple" 出现在"winter"前面,用带stable的函数排序后,他们的次序一定不变,如果你使用的是不带"stable"的函数排序,那么排序完后,"Winter"有可能在"apple"的前面。

1.4 全排序

全排序即把所给定范围所有的元素按照大小关系顺序排列。用于全排序的函数有

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);

template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);

在第1,3种形式中,sort 和 stable_sort都没有指定比较函数,系统会默认使用operator< 对区间[first,last)内的所有元素进行排序, 因此,如果你使用的类型义军已经重载了operator<函数,那么你可以省心了。第2, 4种形式,你可以随意指定比较函数,应用更为灵活一些。来看看实际应用:

班上有10个学生,我想知道他们的成绩排名。

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
using namespace std;

class student{
        public:
        student(const string &a, int b):name(a), score(b){}
        string name;
        int score;
        bool operator < (const student &m)const {
                return score< m.score;
        }
};

int main() {
        vector< student> vect;
        student st1("Tom", 74);
        vect.push_back(st1);
        st1.name="Jimy";
        st1.score=56;
        vect.push_back(st1);
        st1.name="Mary";
        st1.score=92;
        vect.push_back(st1);
        st1.name="Jessy";
        st1.score=85;
        vect.push_back(st1);
        st1.name="Jone";
        st1.score=56;
        vect.push_back(st1);
        st1.name="Bush";
        st1.score=52;
        vect.push_back(st1);
        st1.name="Winter";
        st1.score=77;
        vect.push_back(st1);
        st1.name="Andyer";
        st1.score=63;
        vect.push_back(st1);
        st1.name="Lily";
        st1.score=76;
        vect.push_back(st1);
        st1.name="Maryia";
        st1.score=89;
        vect.push_back(st1);
        cout<<"------before sort..."<<endl;
        for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
        stable_sort(vect.begin(), vect.end(),less<student>());
        cout <<"-----after sort ...."<<endl;
        for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
        return 0 ;
}

其输出是:
------before sort...
Tom:    74
Jimy:   56
Mary:   92
Jessy:  85
Jone:   56
Bush:   52
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89
-----after sort ....
Bush:   52
Jimy:   56
Jone:   56
Andyer: 63
Tom:    74
Lily:   76
Winter: 77
Jessy:  85
Maryia: 89
Mary:   92
sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的快速排序,而是结合内插排序算法)。注1,可以保证很好的平均性能、复杂度为n*log(n),由于单纯的快速排序在理论上有最差的情况,性能很低,其算法复杂度为n*n,但目前大部分的STL版本都已经在这方面做了优化,因此你可以放心使用。stable_sort采用的是"归并排序",分派足够内存是,其算法复杂度为n*log(n), 否则其复杂度为n*log(n)*log(n),其优点是会保持相等元素之间的相对位置在排序前后保持一致。

1.5 局部排序

局部排序其实是为了减少不必要的操作而提供的排序方式。其函数原型为:
template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
StrictWeakOrdering comp);

template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);

template <class InputIterator, class RandomAccessIterator,
class StrictWeakOrdering>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last, Compare comp);

理解了sort 和stable_sort后,再来理解partial_sort 就比较容易了。先看看其用途: 班上有10个学生,我想知道分数最低的5名是哪些人。如果没有partial_sort,你就需要用sort把所有人排好序,然后再取前5个。现在你只需要对分数最低5名排序,把上面的程序做如下修改:
stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());

输出结果为:
------before sort...
Tom:    74
Jimy:   56
Mary:   92
Jessy:  85
Jone:   56
Bush:   52
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89
-----after sort ....
Bush:   52
Jimy:   56
Jone:   56
Andyer: 63
Tom:    74
Mary:   92
Jessy:  85
Winter: 77
Lily:   76
Maryia: 89
这样的好处知道了吗?当数据量小的时候可能看不出优势,如果是100万学生,我想找分数最少的5个人......

partial_sort采用的堆排序(heapsort),它在任何情况下的复杂度都是n*log(n). 如果你希望用partial_sort来实现全排序,你只要让middle=last就可以了。

partial_sort_copy其实是copy和partial_sort的组合。被排序(被复制)的数量是[first, last)和[result_first, result_last)中区间较小的那个。如果[result_first, result_last)区间大于[first, last)区间,那么partial_sort相当于copy和sort的组合。

1.6 nth_element 指定元素排序

nth_element一个容易看懂但解释比较麻烦的排序。用例子说会更方便:
班上有10个学生,我想知道分数排在倒数第4名的学生。
如果要满足上述需求,可以用sort排好序,然后取第4位(因为是由小到大排), 更聪明的朋友会用partial_sort, 只排前4位,然后得到第4位。其实这是你还是浪费,因为前两位你根本没有必要排序,此时,你就需要nth_element:
template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, StrictWeakOrdering comp);

对于上述实例需求,你只需要按下面要求修改1.4中的程序:
stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());

运行结果为:
------before sort...
Tom:    74
Jimy:   56
Mary:   92
Jessy:  85
Jone:   56
Bush:   52
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89
-----after sort ....
Jone:   56
Bush:   52
Jimy:   56
Andyer: 63
Jessy:  85
Mary:   92
Winter: 77
Tom:    74
Lily:   76
Maryia: 89
第四个是谁?Andyer,这个倒霉的家伙。为什么是begin()+3而不是+4? 我开始写这篇文章的时候也没有在意,后来在ilovevc 的提醒下,发现了这个问题。begin()是第一个,begin()+1是第二个,... begin()+3当然就是第四个了。

1.7 partition 和stable_partition

好像这两个函数并不是用来排序的,'分类'算法,会更加贴切一些。partition就是把一个区间中的元素按照某个条件分成两类。其函数原型为:
template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first,
ForwardIterator last, Predicate pred)
template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last,
Predicate pred);

看看应用吧:班上10个学生,计算所有没有及格(低于60分)的学生。你只需要按照下面格式替换1.4中的程序:
stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
student exam("pass", 60);
stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));

其输出结果为:
------before sort...
Tom:    74
Jimy:   56
Mary:   92
Jessy:  85
Jone:   56
Bush:   52
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89
-----after sort ....
Jimy:   56
Jone:   56
Bush:   52
Tom:    74
Mary:   92
Jessy:  85
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89
看见了吗,Jimy,Jone, Bush(难怪说美国总统比较笨 smile )都没有及格。而且使用的是stable_partition, 元素之间的相对次序是没有变.

2 Sort 和容器


STL中标准容器主要vector, list, deque, string, set, multiset, map, multimay, 其中set, multiset, map, multimap都是以树结构的方式存储其元素详细内容请参看:学习STL map, STL set之数据结构基础. 因此在这些容器中,元素一直是有序的。

这些容器的迭代器类型并不是随机型迭代器,因此,上述的那些排序函数,对于这些容器是不可用的。上述sort函数对于下列容器是可用的:

  • vector
  • string
  • deque
如果你自己定义的容器也支持随机型迭代器,那么使用排序算法是没有任何问题的。

对于list容器,list自带一个sort成员函数list::sort(). 它和算法函数中的sort差不多,但是list::sort是基于指针的方式排序,也就是说,所有的数据移动和比较都是此用指针的方式实现,因此排序后的迭代器一直保持有效(vector中sort后的迭代器会失效).

3 选择合适的排序函数


为什么要选择合适的排序函数?可能你并不关心效率(这里的效率指的是程序运行时间), 或者说你的数据量很小, 因此你觉得随便用哪个函数都无关紧要。

其实不然,即使你不关心效率,如果你选择合适的排序函数,你会让你的代码更容易让人明白,你会让你的代码更有扩充性,逐渐养成一个良好的习惯,很重要吧 smile 。

如果你以前有用过C语言中的qsort, 想知道qsort和他们的比较,那我告诉你,qsort和sort是一样的,因为他们采用的都是快速排序。从效率上看,以下几种sort算法的是一个排序,效率由高到低(耗时由小变大):

  1. partion
  2. stable_partition
  3. nth_element
  4. partial_sort
  5. sort
  6. stable_sort
记得,以前翻译过Effective STL的文章,其中对如何选择排序函数总结的很好:
  • 若需对vector, string, deque, 或 array容器进行全排序,你可选择sort或stable_sort;
  • 若只需对vector, string, deque, 或 array容器中取得top n的元素,部分排序partial_sort是首选.
  • 若对于vector, string, deque, 或array容器,你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部顺序,nth_element是最理想的;
  • 若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开,你最好使用partition或stable_partition;
  • 若使用的list容器,你可以直接使用partition和stable_partition算法,你可以使用list::sort代替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果,你必须间接使用。正如上面介绍的有几种方式可以选择。
总之记住一句话: 如果你想节约时间,不要走弯路, 也不要走多余的路!

4 小结


讨论技术就像个无底洞,经常容易由一点可以引申另外无数个技术点。因此需要从全局的角度来观察问题,就像观察STL中的sort算法一样。其实在STL还有make_heap, sort_heap等排序算法。本文章没有提到。本文以实例的方式,解释了STL中排序算法的特性,并总结了在实际情况下应如何选择合适的算法。

5 参考文档

条款31:如何选择排序函数 
The Standard Librarian: Sorting in the Standard Library 
Effective STL中文版 
Standard Template Library Programmer's Guide vvvv
上文转自:https://www.cppblog.com/mzty/archive/2005/12/15/1770.html

--------------------------------------------------------------------------------------------------------------------------------------------------------------

对象数组排序这里展示了两种方法,定义比较函数或通过重载比较运算符使得类本身是可以比较的,就像基本类型一样。
定义比较函数,既可以通过定义比较运算符(如operator <),也可以直接定义函数(如compare)。
重载运算符之后,可以在sort函数中通过less或greater或less_equal等来调整升序还是降序,默认是升序。
另外,重载运算符后,函数bool operator < 就不要了,否则用g++编译出错。

  1. #include <algorithm>     
  2. #include <iostream>     
  3. #include <vector>     
  4. using namespace std;    
  5. class MyClass    
  6. {    
  7. public:    
  8.     int id;    
  9.     MyClass() {}    
  10.     MyClass(int i): id( i ) {}    
  11.     bool operator < ( const MyClass &b ) const    
  12.     {    
  13.          return id < b.id;    
  14.     }    
  15.        
  16.     bool operator > ( const MyClass &b ) const    
  17.     {    
  18.          return id > b.id;    
  19.     }    
  20. };    
  21. /*  
  22. bool operator < ( MyClass a, MyClass b )  
  23.  
  24.     return a.id < b.id;  
  25.  
  26. */    
  27. bool compare( MyClass a, MyClass b )    
  28. {    
  29.     return a.id < b.id;    
  30. }    
  31. int main()    
  32. {    
  33.     //数组     
  34.     cout<<"数组"<<endl;    
  35.     MyClass arr[10];    
  36.     srand(time(NULL));    
  37.     forint i = 0; i < 10; i++ )    
  38.         arr[i].id = rand()%101;    
  39.     cout<<"before sort"<<endl;    
  40.     forint i = 0; i < 10; i++ )    
  41.         cout<<arr[i].id<<endl;    
  42.        
  43.     sort(arr,arr+10,less<MyClass>());    
  44.     cout<<"after sort"<<endl;    
  45.     forint i = 0; i < 10; i++ )    
  46.         cout<<arr[i].id<<endl;    
  47.     //动态数组vector     
  48.     cout<<"动态数组vector"<<endl;    
  49.     vector<MyClass> list;    
  50.     forint i = 0; i < 10; i++ )    
  51.         list.push_back( MyClass( rand()%101 ) );    
  52.     cout<<"before sort"<<endl;    
  53.     forint i = 0; i < 10; i++ )    
  54.         cout<<list[i].id<<endl;    
  55.        
  56.     sort(list.begin(),list.end(),greater<MyClass>());    
  57.     cout<<"after sort"<<endl;    
  58.     forint i = 0; i < 10; i++ )    
  59.         cout<<list[i].id<<endl;    
  60.        
  61.     //定义比较函数     
  62.     cout<<"定义比较函数"<<endl;    
  63.     vector<MyClass> list2;    
  64.     forint i = 0; i < 10; i++ )    
  65.         list2.push_back( MyClass( rand()%101 ) );    
  66.     cout<<"before sort"<<endl;    
  67.     forint i = 0; i < 10; i++ )    
  68.         cout<<list2[i].id<<endl;    
  69.        
  70.     sort(list2.begin(),list2.end(),compare);    
  71.     cout<<"after sort"<<endl;    
  72.     forint i = 0; i < 10; i++ )    
  73.         cout<<list2[i].id<<endl;    
  74.            
  75.     //使得类本身就是可以比较的     
  76.     cout<<"使得类本身就是可以比较的"<<endl;    
  77.     vector<MyClass> list3;    
  78.     forint i = 0; i < 10; i++ )    
  79.         list3.push_back( MyClass( rand()%101 ) );    
  80.     cout<<"before sort"<<endl;    
  81.     forint i = 0; i < 10; i++ )    
  82.         cout<<list3[i].id<<endl;    
  83.        
  84.     sort(list3.begin(),list3.end());    
  85.     cout<<"after sort"<<endl;    
  86.     forint i = 0; i < 10; i++ )    
  87.         cout<<list3[i].id<<endl;    
  88.        
  89.     return 0;    
  90. }    

sort函数是一个比较方便使用的STL函数,可以直接来进行各种排序。 

由于在工作的时候有一个排序,刚开始没怎么注意!就用sort算法来实现了,后来出现了一些问题才导致我才对sort算法的一些注意事项的总结: 

1.       sort 算法函数的用法。

vector<int> vect;

//….

Sort(vect.begin(),vect.end();

//相当于下面的调用

Sort(vect.begin(),vect.end(),less<int>()); //如果不提供比较函数是系统默认从小到大排序

当我们要按某种方式进行排序时,需要指定自己的排序函数,否则系统默认提供一个比较函数。

2.Sort用法挺简单,不过在这儿打算介绍一下值得注意的一点地方。

看下面程序(1):

  1. #include <algorithm>   
  2. #include <iostream>   
  3. #include <string>   
  4. #include <vector>   
  5.    
  6. using namespace std;  
  7.    
  8. class A  
  9. {  
  10. public:  
  11.     A()  
  12.          {  
  13.         dict.push_back("owen");  
  14.         dict.push_back("messi");  
  15.         dict.push_back("figo");  
  16.     }  
  17.      
  18.     int less(const string &s1, const string &s2)  
  19.          {  
  20.         return s1 < s2;  
  21.     }  
  22.    
  23.     void Sort()  
  24.          {  
  25.         sort(dict.begin(), dict.end(), less);  
  26.     }  
  27.     void output()  
  28.          {  
  29.         for(vector<string>::iterator iter=dict.begin(); iter !=dict.end(); ++iter)  
  30.             cout << *iter << endl;  
  31.     }  
  32. private:  
  33.     vector<string> dict;  
  34. };  
  35.    
  36. int main() {  
  37.     A myclass;  
  38.     myclass.output();  
  39.     myclass.Sort();  
  40.     myclass.output();  
  41.    
  42.     return 0;  
  43. }  

编译的时候就报错。Why?难道不是这么用的。。。。

下面我们来看看 正确的例子(2):

  1. #include <algorithm>   
  2. #include <iostream>   
  3. #include <string>   
  4. #include <vector>    
  5. using namespace std;  
  6.    
  7. int less(const string &s1,const string &s2)  
  8. {  
  9.          return s1<s2;  
  10. }  
  11. class A  
  12. {  
  13. public:  
  14.     A()  
  15.          {  
  16.         dict.push_back("owen");  
  17.         dict.push_back("messi");  
  18.         dict.push_back("figo");  
  19.     }  
  20.     void Sort()  
  21.          {  
  22.         sort(dict.begin(), dict.end(), less);  
  23.     }  
  24.     void output()  
  25.          {  
  26.         for(vector<string>::iterator iter=dict.begin(); iter !=dict.end(); ++iter)  
  27.             cout << *iter << endl;  
  28.     }  
  29. private:  
  30.     vector<string> dict;  
  31. };  
  32.    
  33. int main() {  
  34.     A myclass;  
  35.     myclass.output();  
  36.     myclass.Sort();  
  37.     myclass.output();  
  38.    
  39.     return 0;  
  40. }  

这个例子是正确的! 为什么有这个差异?这个问题出在哪儿,思考下上面两个例子的不同! 也许你不难发现其中的问题?this指针!!

例(1)中发现 int less(const string &s1, const string &s2)也就相当于int less( A* const this,const string &s1,const string &s2) 所以问题的答案一目了然!所以有两种解决方法:

1)  利用类的静态函数---面向类的属性、。

2)  利用仿函数来实现比较函数。

以上两种方法都巧妙的避开了this指针。当然以上部分还是为了解决下面的话题! 如果有这样的一个类 A中有成员int x.而类B 中有成员vector<A> vec.map<int,类C>mapVec .这样的情况对vector<A>vec,以A中的X 作为map表的索引排序。

类A   int x;

类C   int y;l

类B   map<int,C>mapVec;  vector<A> vec;对vector<A>用sort算法排序,其中A作为map表的索引查找C 类中的Y来进行排序。这儿问题就来了?如上面所说在B类中的Sort()-中的 sort()函数的比较函数如何写?  我们来看下伪代码:

  1. Class A{  
  2.          public:  
  3.                    Int  x;  
  4. };  
  5. Class C{  
  6.          public:  
  7.                    Int  y;  
  8. };  
  9. Class B{  
  10. Public:  
  11. B(){};  
  12. Void Sort()  
  13. {  
  14. Sort(vec.begin(),vec.end(),比较函数);  
  15. }  
  16. private:  
  17.                    Vector<A> vec;  
  18.                    Map<int,C> mapVec;  
  19. };  

当然看到这个问题也许第一影响应该是在Sort()中做一个快排就可以,当然这样可以。不过让我们结合上面的例子想想这个问题如果用纯STL的方法如何解决。

1.       利用类的静态函数-----这个方法当然不行。静态函数是类的属性而我们需要map表。

2.       利用仿函数来解决。

那这个仿函数如何来写?---仿函数中需要有map<int,C>表,且不能是通过this指针带入的。好了基于上面的我们来看下例子3:

  1. #include <iostream>   
  2. #include <algorithm>   
  3. #include <vector>   
  4. #include <map>   
  5. using namespace std;  
  6.    
  7. class A  
  8. {  
  9. public:  
  10.     int x;  
  11. };  
  12.    
  13. class C//XXX  
  14. {  
  15. public:  
  16.     int y;  
  17. };  
  18.    
  19. class B  
  20. {  
  21. public:  
  22.     B():cmp(mapVec)  
  23.     {  
  24.          
  25.     }  
  26.    
  27.     void Sort()  
  28.     {  
  29.         sort(vec.begin(),vec.end(),cmp);  
  30.     }  
  31.    
  32. protected:  
  33.     class InnerCmp  
  34.     {  
  35.     public:  
  36.         InnerCmp(map<int,C> &map):m(map)  
  37.         {  
  38.         }  
  39.    
  40.         bool operator() (const A &a,const A &b) const  
  41.         {  
  42.             return m[a.x].y<m[b.x].y;  
  43.         }  
  44.    
  45.     private:  
  46.         map<int,C> &m;  
  47.     };  
  48.    
  49. private:  
  50.     const InnerCmp cmp;  
  51.     vector<A> vec;  
  52.     map<int,C> mapVec;  
  53. };  
  54.    
  55. int main()  
  56. {  
  57.     return 0;  
  58. }  

如上面的例子,我们构造的仿函数完全符合规则。同时巧妙的把map 放到类InnerCmp中。这样我们就可以达到上面问题的目的。当然这样做只是为了更好的理解 比较函数。


以上来自互联网,在此表示感谢

 

贪心——NYOJ题目106 背包问题

 

背包问题

时间限制:3000 ms  |  内存限制:65535 KB
难度:3
描述
现在有很多物品(它们是可以分割的),我们知道它们每个物品的单位重量的价值v和重量w(1<=v,w<=10);如果给你一个背包它能容纳的重量为m(10<=m<=20),你所要做的就是把物品装到背包里,使背包里的物品的价值总和最大。
输入
第一行输入一个正整数n(1<=n<=5),表示有n组测试数据;
随后有n测试数据,每组测试数据的第一行有两个正整数s,m(1<=s<=10);s表示有s个物品。接下来的s行每行有两个正整数v,w。
输出
输出每组测试数据中背包内的物品的价值和,每次输出占一行。
样例输入
1
3 15
5 10
2 8
3 9
样例输出
65

分析:贪心原理,要求背包物品总价值最大,故尽可能多存放价值大的物品;如图 题目中给出的例子, 背包可容纳重量15,故先放价值最大的A,将10斤A全部放入背包,然后放入价值次大的C,此时背包容纳量剩下15-10=5,而C还有9斤,因此剩下的全放C,总价值=(10*5)+(5*3)=65

代码:

 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>

using namespace std;

typedef struct GOODS
{
	int v,w;//价值和重量都比较小<256 
}GOODS;

GOODS goods [10];

int cmp(const void * a,const void *b)
{
	return (*(GOODS *)a).v<  (*(GOODS *)b).v ? 1: -1;
}
int main()
{
	int s,n,m,i;
	int value,weight;
    scanf("%d",&n);
    while(n--)
    {
              scanf("%d%d",&s,&m);
              for(i=0;i<s;i++)     scanf("%d%d",&goods[i].v,&goods[i].w); 
			 qsort(goods,s,sizeof(goods[0]),cmp);  //将物品按价值从大到小排序 
			 //for(i=0;i<s;i++) printf("%d %d\n",goods[i].v,goods[i].w);
			 value = weight = i = 0;
			 
			 while(m)
			 {
					if(goods[i].w <= m)//这种物品的总质量 还小与目前背包容纳量,则全部装入 
					{
						m -= goods[i].w;
						value += goods[i].v *goods[i].w; //w重量的单价为v的物品价值 
					}
					else//将背包剩下的容量全部装这种物品 
					{
						value += goods[i].v * m; 
						m=0;
					} 
				
				i++;
			}   
			printf("%d\n",value);    
    }
  // system("pause");
 return 0;    
}        


 

贪心——NYOJ 题目71 独木舟上的旅行

独木舟上的旅行

时间限制:3000 ms  |  内存限制:65535 KB
难度:2
描述

进行一次独木舟的旅行活动,独木舟可以在港口租到,并且之间没有区别。一条独木舟最多只能乘坐两个人,且乘客的总重量不能超过独木舟的最大承载量。我们要尽量减少这次活动中的花销,所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序,读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给出的规则,计算要安置所有旅客必须的最少的独木舟条数,并输出结果。

输入
第一行输入s,表示测试数据的组数;
每组数据的第一行包括两个整数w,n,80<=w<=200,1<=n<=300,w为一条独木舟的最大承载量,n为人数;
接下来的一组数据为每个人的重量(不能大于船的承载量);
输出
每组人数所需要的最少独木舟的条数。
样例输入
3
85 6
5 84 85 80 84 83
90 3
90 45 60
100 5
50 50 90 40 60
样例输出
5
3
3

分析:要求使用的独木舟最少,而且题目是每个最多承载两个人,每个独木舟都有最大载重,故要尽量使每个独木舟装载尽可能多的乘客,可以将乘客质量按总小到大排序,然后以质量大的优先使用独木舟和质量小得结合,以此类推,得到使用最少的独木舟。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>

using namespace std;

int weight[301];

int main()
{
    int n,m,w,i,j,cnt;
    scanf("%d",&n);
    while(n--)
    {
              scanf("%d%d",&w,&m);
              for(i=1;i<=m;i++) 
                   scanf("%d",&weight[i]); 
               sort(weight+1,weight+m+1) ;//质量排序
		//qsort(weight,m,sizeof(int),cmp); 因为是从下表1到m排序,这样写不对 
		// for(i=1;i<=m;i++) printf("%d\n",weight[i]);
			 cnt = 0;
			 for(i=1,j=m;i<j;)
			 {
				if(weight[i]+weight[j] <= w)// 质量大的跟质量小的可以乘坐一个 
				{
					cnt++;
					i++;j--; //乘客减少两个 
				}
				else  //质量太大不能和小的结合,故自己使用一个 
				{
					cnt++;
					j--; //乘客减少1个 
				} 
			}   
			if(i==j) cnt++; //如果最后剩下中间一个乘客 ,cnt++ 
			printf("%d\n",cnt);    
    }
   //system("pause");
 return 0;    
}


 

贪心——NYOJ 题目6 喷水装置(一)

喷水装置(一)

时间限制:3000 ms  |  内存限制:65535 KB
难度:3
描述
现有一块草坪,长为20米,宽为2米,要在横中心线上放置半径为Ri的喷水装置,每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润,这有充足的喷水装置i(1<i<600)个,并且一定能把草坪全部湿润,你要做的是:选择尽量少的喷水装置,把整个草坪的全部湿润。
输入
第一行m表示有m组测试数据
每一组测试数据的第一行有一个整数数n,n表示共有n个喷水装置,随后的一行,有n个实数ri,ri表示该喷水装置能覆盖的圆的半径。
输出
输出所用装置的个数
样例输入
2
5
2 3.2 4 4.5 6 
10
1 2 3 1 2 1.2 3 1.1 1 2
样例输出
2
5

 

分析:

优先使用半径大的,来达到最大的覆盖面积,可以先对半径进行排序,计算出大的喷水装置所能覆盖的最大长度(因为在中心横线,长度能覆盖完,宽度肯定也覆盖了)

来计算每个喷水装置所能覆盖的长度

 

 

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

double r[601];


int  cmp(const void * a,const void * b)
{
    return *(double *)a < *(double*)b ? 1:-1; //从大到小 
}
int main()
{
    int m,n,i,j;
    double length;
    scanf("%d",&m);
    while(m--)
    {
           scanf("%d",&n);
           for(i=0;i<n;i++)  scanf("%lf",&r[i]);  
           qsort(r,n,sizeof(double),cmp);//将半径从大到小排序 
           //for(i=0;i<n;i++)  printf("%lf\n",r[i]);
           int cnt = 1;
           length = 0;//设置i为上一个已安排活动
           for(j=0;j<n;j++)
           {
                 length += 2 * sqrt(r[j]*r[j]-1);//每一个喷水装置所能覆盖的面积的最大长度  
                 if(length>=20.0) break;
                 cnt++;                              
           }
           printf("%d\n",cnt);
    }
   //system("PAUSE");
    return 0;    
}        

贪心——NYOJ 题目14 会场安排问题

                                        会场安排问题

时间限制:3000 ms  |  内存限制:65535 KB
难度:4
描述
学校的小礼堂每天都会有许多活动,有时间这些活动的计划时间会发生冲突,需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动,每个时间最多安排一个活动。现在小刘有一些活动计划的时间表,他想尽可能的安排更多的活动,请问他该如何安排。
输入
第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。
随后的n行,每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间(Bi<=Ei)
输出
对于每一组输入,输出最多能够安排的活动数量。
每组的输出占一行
样例输入
2
2
1 10
10 11
3
1 10
10 11
11 20
样例输出
1
2
提示
注意:如果上一个活动在t时间结束,下一个活动最早应该在t+1时

分析:  做这道题目的时候,我们先来想一下下面的情况:如果有两个活动让你选择一个,它们的结束时间一前一后,那么,我们应该选择哪一个才能有利于之后选取更多的活动呢?  很明显,我们应该选择的是结束时间较早的那个活动。  同样,在有一大堆活动时,我们最先应该选择结束时间最早的那个,以利于之后能安排更多的活动,然后,再在剩下的可选的会场中选择最可能结束时间最早的那个,依次类推,直到无法安排任何活动为止。  也就是说,每次选择时,都应该贪婪的选择结束时间最短的那个活动。 现在我们来证明刚才的贪心方法是正确的:假设有哪一次选择的不是结束时间最早的那个活动,那么,此次选择之后,剩下的可选活动一定没有选择结束时间最早的活动时多,用这种方法之后可再选择的活动数目一定不会比上面思路中的方法更多。

 

代码:

 
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>

using namespace std;

typedef struct Party
{
     int start,end;        
}Party;

Party PARTY[10001];


int  cmp(const void * a,const void * b)
{
    return (*(Party *)a).end > (*(Party*)b).end ? 1:-1;
}
int main()
{
    int m,n,i,j;
    scanf("%d",&m);
    while(m--)
    {
           scanf("%d",&n);
           for(i=0;i<n;i++)  scanf("%d%d",&PARTY[i].start,&PARTY[i].end);  
           qsort(PARTY,n,sizeof(Party),cmp);
           //for(i=0;i<n;i++)  printf("%d %d\n",PARTY[i].start,PARTY[i].end);
           int cnt = 1;
           i = 0;//设置i为上一个已安排活动
           for(j=1;j<n;j++)
           {
                 if(PARTY[i].end<PARTY[j].start) 
                 {
                    cnt++;
                    i = j;//安排一个活动之后 i 的值变化为已安排的活动                        
                 }
           }
           printf("%d\n",cnt);
    }
   // system("PAUSE");
    return 0;    
}        


时间:88 内存:388

ACM—NYOJ小小结

我觉得做题不是越多越好,而是善于总结!

做南阳理工题目也有一段时间了,我觉得还是有必要总结一下,把以前做过的题目再重新看看,提取其中的知识点,重点,达到灵活运用才是王道!


算法的五个特点: 1. 能行性(或有效的)  2. 有限性 3. 确定性 4. 输入 5. 输出


一、基本输入:

每道题目基本上都要求输入数据,因此你的程序要准确接收输入的数据,这步做好了,下面的才有可能进行,并且输入都得有个结束标示,不然一直输入是不可能的吧。下面对这些基本的输入做些总结。

1. 先输入一个整数,代表测试数据组数 

例如:第一行输入一个数N(0<N<=100),表示有N组测试数据


 我一般这样写代码

int n;
scanf("%d",&n);
while(n--)
{
     //........核心程序
}
这样看起来简洁,直接n--

不过结尾如果要求输出 case n : .....

用个for循环比较好,循环一次,case++;


2.没有说明几组测试数据的,一般是以EOF结束输入,或者指明EOF结束

C语法:
	while( scanf("%d %d",&a, &b) != EOF) 
	{     .... } 
C++语法:
	while( cin >> a >> b ) {     .... } 

Scanf函数返回值就是读出的变量个数,

如:scanf( “%d  %d”, &a, &b ); 如果a和b都被成功读入整数,那么scanf的返回值就是2; 如果只有a被成功读入整数,返回值为1;

如果a和b都未被成功读入整数,返回值为0;

如果遇到错误或遇到end of file,返回值为EOF 
EOF是一个预定义的常量,等于-1。

3.输入不说明有多少个Input Block,但以某个特殊输入为结束标志。

Input contains multiple test cases. Each test case contains a pair of integers a and b, one pair of integers per line. 

A test case containing 0 0 terminates the input and this test case is not to be processed. 

2010-10-13
20
本类输入解决方案:

C语法:
while(scanf("%d",&n)  && n!=0 ) { .... } 

C++语法:
while( cin >> n && n != 0 ) { .... }

4.输入是一整行字符串的:

C语法:
	  char buf[20];   gets(buf); 
C++语法:
	如果用string buf;来保存:getline( cin , buf ); 
	如果用char buf[ 255 ]; 来保存: cin.getline( buf, 255 );

scanf(“ %s%s”,str1,str2),在多个字符串之间用一个或多个空格分隔;


若使用gets函数,应为gets(str1); gets(str2); 字符串之间用回车符作分隔。


通常情况下,接受短字符用scanf函数,接受长字符用gets函数。


而getchar函数每次只接受一个字符,经常c=getchar()这样来使用。


getline 是一个函数,它可以接受用户的输入的字符,直到已达指定个数,或者用户输入了特定的字符。它的函数声明形式(函数原型)如下:
iostream& getline(char line[], int size, char endchar = '\n');
不用管它的返回类型,来关心它的三个参数:
char line[]: 就是一个字符数组,用户输入的内容将存入在该数组内。
int size : 最多接受几个字符?用户超过size的输入都将不被接受。
char endchar :当用户输入endchar指定的字符时,自动结束。默认是回车符。

结合后两个参数,getline可以方便地实现: 用户最多输入指定个数的字符,如果超过,则仅指定个数的前面字符有效,如果没有超过,则用户可以通过回车来结束输入。
char name[4];
cin.getline(name,4,'\n');
由于 endchar 默认已经是 '\n',所以后面那行也可以写成:
cin.getline(name,4);


5.接受字符串,以一个空行结束

while( gets(str) )
{....}

(粘贴吧,太累了。。)

二、输出问题

 一个Input Block对应一个Output Block,OutputBlock之间空行。

l  ProblemDescription
Your task is to calculate the sum of some integers.

l  Input
Input contains an integer N in the first line, and then N lines follow. Eachline starts with a integer M, and then M integers follow in the same line.

l  Output
For each group of input integers you should output their sum in one line, andyou must note that there is a blank line between outputs. 

l  Sampleinput
3
4 1 2 3 4
5 1 2 3 4 5
3 1 2 3

l  Sampleoutput
10

15

6


 C语法:

 { 
    .... 
   printf("%d\n\n",ans);

}

C++语法:

 { 
    ... 
    cout << ans << endl<< endl; 
}

2.输出数据中间有空行,最后一个数据后面没有空行


C语法:

 for (k=0;k<count;k++) 
{ 
      while (…) 
      { 
             printf(" %d\n",result); 
      } 
      if (k!=count-1) printf("\n"); 
} 



 

https://acm.hdu.edu.cn/showproblem.php?pid=1016

https://acm.hdu.edu.cn/showproblem.php?pid=1017

 

初学者常见问题

编译错误

l Main函数必须返回int类型(正式比赛)

l  不要在for语句中定义类型

l __int64不支持,可以用long long代替

l  使用了汉语的标点符号

l  itoa不是ANSI函数

  能将整数转换为字符串而且与ANSI标准兼容的方法是使用sprintf()函数

        int num = 100;
    char str[25];
    sprintf(str, " %d" , num);

l  另外,拷贝程序容易产生错误

不常规的编程方式

l  Printf和cout混用的问题

l  以下的程序输出什么?

l  #include<stdio.h>

l  #include<iostream.h>

l  int main()

l  {

l       int j=0;

l       for(j=0;j<5;j++)

l       {

l              cout<<"j=";

l              printf("%d\n",j);

l       }

l       return 0;

l  }

 

什么问题?

l  一个带缓冲输出(cout)

l   一个不带缓冲输出(printf)

l  Goole你的问题,充分利用网络资源



ACM菜鸟的21个经典错误

HDU1089 AB为例

l SampleInput

l 1 5

l 10 20

l SampleOutput

l 6

l 30

菜鸟之伤(1

 #include<stdio.h>

void main()

{

l int a,b;

scanf(“%d%d”,&a,&b);

printf(“%d\n”,a+b);

 }


菜鸟之伤(1

l  总结:

     程序不能处理多组数据的问题是最常见的入门问题,只要掌握几种常见的类型,就可以轻松掌握了,具体处理方法曾在第一次课件有详细描述,这里省略了~

菜鸟之伤(2

#include<stdio.h>
 void main()
{
  int a,b;
  while(scanf(“%d%d”,&a,&b)!=0)
  printf(“%d\n”,a+b);
}


菜鸟之伤(2

l  总结:文件结束符EOF的值是-1而不是0,所以while(scanf(…)!=0)常常会因为死循环而造成TLE,这个必须牢记。

l  说明:不仅仅菜鸟,很多老鸟也常常因为不注意这点而犯错误,而且还常常因为想不到会犯这种低级错误而想不到原因。

菜鸟之伤(3

#include<stdio.h>

void main()
{

   int a,b;

   while(scanf(“%d%d”,&a,&b)!=EOF);  //这里多了分号

   printf(“%d\n”,a+b);

 }


菜鸟之伤(3

l  总结:while 或者 for循环的条件外面误加了分号,编译不影响,但是结果循环体没有真正得到多次执行;

l  说明:菜鸟常犯的错误,往往因为编译能通过而不能迅速察觉,尤其比赛中~

提醒:当你将scanf();语句加上while循环以处理多组数据问题的时候尤其注意——因为之前有分号,很容易忘记去掉!

菜鸟之伤(4

 #include<stdio.h>

 void main()

 {

   int a,b;

   while(scanf(“%d%d”,&a,&b) =2) //应为-1 或 EOF

      printf(“%d\n”,a+b);

}


菜鸟之伤(4

l  总结:

       C语言中,赋值符号=和判断是否相等的逻辑符号==具有完全不同的含义,往往因为我们的习惯问题,在编程中误将判断是否相等的逻辑符号写成赋值符号=。同样的,这种失误也会因为不影响编译而影响查错的时间。

 

l  说明:菜鸟常犯的错误,但是有过几次教训就会牢记了,呵呵~

HDU1001 Sum Problem为例

l SampleInput

l 1

l 100

l SampleOutput

l 1

 

l 5050

 

菜鸟之伤(5

#include<stdio.h>

void main()

{    int i,n,s;

     while(scanf(“%d”,&n) ==1)

     {

          for(i=1;i<=n;i++)

              s+=i; //s为初始化

          printf(“%d\n\n”,s);

     }

}


菜鸟之伤(5

l  总结:

     忘记变量的初始化是典型的菜鸟问题,不必紧张,多经历几次就牢记了~

 

说明:普通变量的初始化还比较容易查找,而用来保存计算结果的数组的初始化更是容易忘记!

菜鸟之伤(6

#include<stdio.h>

void main()

{    int i,n,s=0;

     while(scanf(“%d”,&n) ==1)

     {

          for(i=1;i<=n;i++)

              s+=i; //第二次循环s的初始值不一定为0

          printf(“%d\n\n”,s);

     }

}


菜鸟之伤(6

l  总结:变量初始化放在循环外,是一个典型的ACM初级错误,因为ACM赛题的多组测试特性,如果不能在循环内初始化,将只能确保第一组数据没问题,而很多入门者习惯只测试一组数据,很容易忽略这个问题

l     

l  说明:菜鸟常犯的错误,关键是要理解为什么这样会有问题,真正理解后,修改也就不难了。

菜鸟之伤(7

 #include<stdio.h>

 void main()

 {int i,n,s;

  while(scanf(“%d”,&n) ==1)

  {

     s=n*(n+1)/2; //s有可能越界溢出

     printf(“%d\n\n”,s);

 }

}


菜鸟之伤(7

l  总结:

       数组越界还能在提交后收到Runtime Error的信息反馈,而运算中的数据溢出则往往只能收到Wrong Answer的错误提示,所以这种错误往往容易被误导成算法问题;

      

l  说明:

       不仅菜鸟,就是大牛甚至大神,也常常犯这种错误,只是情况复杂些而已~

菜鸟之伤(8

#include<stdio.h>

void main()

{int i,n,s;

 while(scanf(“%d”,&n) ==1)

 {

 s=n/2*(n+1);

 printf(“%d\n\n”,s);//结果为整数

 }

}


菜鸟之伤(8

l  总结:

     当两个整数进行运算的时候,运算结果一定还是整数,所以不要因为常规数学惯性思维的影响而认为结果可能为浮点数;

     而不同数据类型一同运算的时候,运算结果的数据类型和相对复杂的类型一致(比如 整数+实数,结果类型是实数)

    

菜鸟之伤(9

#include<stdio.h>

void main()

{    int i,n,s;

     while(scanf(“%d”,&n)==1) //丢失大括号,使得循环体不完整而出错

          if(n%2==0)

            s=n/2*(n+1);

           else

               s=(n+1)/2*n;

      printf(“%d\n\n”,s);

 }


菜鸟之伤(9

l  总结:

     写for或者while等任何循环语句的时候,不管循环体内有几个语句,务必养成都加上一对大括号的好习惯。

l  常常碰到的情况是这样的——本来循环体内只有一条语句,确实不用大括号,但是在修改程序的过程中,循环体内增加了其他语句,而这时却忘记了添加大括号!

所以说——好习惯很重要!

菜鸟之伤(10

#include<stdio.h>

void main()

{    int i,n,s;

      while(scanf(“%d”,&n)==1)

       { if(n%2==0)

              s=n/2*(n+1);

           else

               s=(n+1)/2*n;     }

       printf(“%d\n\n”,s); //没包含到大括号里面,没有循环

}


菜鸟之伤(10

l  总结:

     这也是一个经典错误,虽然为循环体加了大括号,但是并没有包含全部的信息,造成的后果是只有一次输出——尽管对于每组数据都处理了,但是只输出最后一组结果。

由于很多同学习惯每次只测试一组数据,就更容易忽略这个错误了...

再次证明——好习惯很重要!

菜鸟之伤(11

l  假设不会中间溢出,下面的程序是否有问题?

l  #include<stdio.h>

l  void main()

l  {    int i,n,s;

l       while(scanf(“%d”,&n) ==1)

l       {

l            s=n(n+1)/2;

l            printf(“%d\n\n”,s);

l       }

l  }

菜鸟之伤(11

l  总结:

     这也是受数学习惯影响而可能出现的一个错误,当然,这个错误很好检查,因为编译不能通过的~

l 总结出这个只是因为确实会出现这个情况,而对于极度没有编程经验的同学来说,有时候也会带来困扰~

    

还是以A+B为例

l  题目描述:计算A+B的值,输入数据每行包含2个正整数,如果输入数据是两个负数,则结束输入。

l SampleInput

l 1 5

l -1 -1

l SampleOutput

l 6

菜鸟之伤(12

#include<stdio.h>

void main()

{
    int a,b;

     while(scanf(“%d%d”,&a,&b)==2)

    {  if(a==-1& b==-1) return; //相与应用 &&

     printf(“%d\n”,a+b);

    }     }


菜鸟之伤(12

l 总结:正如判断相等要用“==”一样,C语言中进行逻辑与的运算也是需要两个字符“&&”,类似的逻辑或运算也是两个字符“||”,如果是单个的字符,含义就完全不同了~

菜鸟之伤(13

l   上一个程序的改进版:

#include<stdio.h>

void main()

{

   int a,b;

   while(scanf(“%d%d”,&a,&b)==2)

  { if(a==-1&& b==-1) return;

   printf(“%d\n”,a+b);

  }   }


菜鸟之伤(13

l  总结:题目描述是负数结束输入,Sample Input最后给出的是-1,如果读题不仔细,很容易陷入思维定势,而会不加思索在程序中用-1判断,这样就真的会发生不幸的事件——尽管我也认为这个陷阱有点阴,而且未必有很大意义,但是题目并没错,而你确实读题不仔细~

      

l  说明:算是经典的小陷阱,现在很少出现了

继续以A+B为例

l 题目描述:给定2个整数A和B,如果A+B>0,请输出”OK!”,否则请输出”No~”

l SampleInput

l 1 5

l 1 -5

l SampleOutput

l OK!

l No~

菜鸟之伤(14

#include<stdio.h>

void main()

{

 int a,b;

 while(scanf(“%d%d”,&a,&b)==2)

 {if(a+b>0)   printf(“OK!\n”);

  else            printf(“NO~\n”);   } //大小写与题目不符

 }


菜鸟之伤(14

l  总结:字符串输出的大小写问题对于菜鸟需要特别注意,其实,不管是——全大写、全小写,还是首字母大写,你尽管复制即可(没有电子版,另当别论),当然还要注意是否有标点符号等情况。

    

l  说明:菜鸟常犯错误,稍有经验即可避免

1170Balloon Comes!为例

l SampleInput

l 4

l + 1 2

l - 1 2

l * 1 2

l / 1 2

菜鸟之伤(15

  int n,a,b,i;

  char p;

  scanf("%d",&n);

  for(i=0;i<n;i++)

  {

      scanf("%c%d%d",&p,&a,&b); // 第一个%c接受的可能是输入n之后的换行符

      if( ……)

  }


菜鸟之伤(15

刚才程序的改进版:

  int n,a,b,i;

  char p;

  scanf("%d",&n);

  getchar(); //这里吸收输入n之后的 ''

  for(i=0;i<n;i++)

  {

      scanf("%c%d%d",&p,&a,&b);

      if( ...) ……

  }


l  是否还有问题?如何修改? (只接受的第一次的'\n')

菜鸟之伤(15

l  总结:字符和数字的混合输入带来的问题,也是一个常常困扰使用C语言编程的同学的经典问题,关键就是程序未能及时接收回车符,而误将回车当作下一组数据的首字母,你可以通过添加一句getchar(); 轻松解决该问题。

      

l  说明:菜鸟的经典错误,如果之前没有遇到过,很难一下子反应过来,当然,遇到一次以后就不成为问题了~

2007 平方和与立方和

l  给定一段连续的整数,求出他们中所有偶数的平方和以及所有奇数的立方和。

l SampleInput

l 1 3

l 2 5

l SampleOutput

l 4 28

l 20 152

菜鸟之伤(16

#include<stdio.h>

void main()

{    int m,n;

     while(scanf(“%d%d” ,&m,&n) ==2)

     {   int i,x=0,y=0;

          for(i=m;i<=n;i++)

          {   if(i%2==0)  y=y+i*i;

               else  x=x+i*i*i;   }

          printf(“%d %d\n”,y,x);

     }

}


菜鸟之伤(16

l  总结:题目并没有保证数据是递增的,但人往往有思维定势,而很多题目的设计就是针对这一点!不要埋怨,这种训练能很好的培养我们审慎的思维习惯。

 

l  说明:这种错误经历过以后还是比较容易牢记的,所以说有时候经验很重要。

菜鸟之伤(17

l  以下的程序输出什么?

#include<stdio.h>

#include<iostream.h>

int main()

{

     int j=0;

     for(j=0;j<5;j++)

     {

           cout<<"j=";  // 尽量不要c与c++混合使用

          printf("%d\n",j);

    }

    return 0;

}


菜鸟之伤(17

l   期望输出:

 

l j=0

l j=1

l j=2

l j=3

l j=4

 

菜鸟之伤(17

l  总结:在一个程序中同时使用C和C++的输出语句,很容易带来问题,原因就是输出机制不完全一样(一个不带缓冲,一个带缓冲),所以尽量避免C和C++输出语句混用。

    

l 说明:这是传说中的经典错误,据说曾困扰某牛人于现场赛 :-)

2004成绩转换为例

题目描述:输入一个百分制的成绩t,将其转换成对应的等级,具体转换规则如下:

         90~100为A;

         80~89为B;

         70~79为C;

         60~69为D;

         0~59为E;

输出描述:对于每组输入数据,输出一行。如果输入数据不在0~100范围内,请输出一行:“Score iserror!”。

菜鸟之伤(18

#include<stdio.h>

int main()

{    int t,a;

       while(scanf("%d",&t)!=EOF)

       {    if(t>100||t<0) printf("Score iserror!\n");

            else

            {  a=(t-50)/10;

               switch(a) //注意case的break;

               {  case 5:

                  case4:printf("A\n");       case3:printf("B\n");

                  case2:printf("C\n");       case1:printf("D\n");

                  default:printf("E\n");     

                }     }    }

               return 0;

       }


菜鸟之伤(18

l  总结:C语言中的case语句要求在每个case的处理后面都要跟break;(特殊需求除外),而如果因为不了解或者不小心而缺少部分break;则执行的效果也许会不符合你最初的设计。

    

l  说明:C语言的基本功很重要~

2046骨牌铺方格为例

题目描述:在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.

输入描述:输入数据由多行组成,每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n(0<n<=50)。

菜鸟之伤(19

#include<stdio.h>

int main()

{

    int i;

     __int64 a[50]={0,1,2};//数组开的小

      for(i=3;i<=50;i++)

         a[i]=a[i-1]+a[i-2];

    while(scanf("%d",&i)!=EOF){

          printf("%I64d\n",a[i]);   

     }

}


菜鸟之伤(19

l 总结:数组下标越界是最常见的Runtime Error,也是菜鸟常犯的错误,除了需要扎实的C语言基本功,编程中的注意力集中也是需要的(很多时候不是不知道理论,而是不注意)~

l 说明:一般情况,你可以通过将数组开的大点而尽量避免这个问题~

1425Sort为例

题目描述:给你n个整数,请按从大到小的顺序输出其中前m大的数。

输入描述:每组测试数据有两行,第一行有两个数n,m(0<n,m<1000000),第二行包含n个各不相同,且都处于区间[-500000,500000]的整数。

菜鸟之伤(20

#include<stdio.h>

void main()

{

   int n,m,i,num[1000000]; //大数组尽量放在main函数外面,全局变量

    while(scanf(“%d%d”,&n,&m)==2)

    {   ......   }

}


菜鸟之伤(20

l  总结:ACM编程中,使用很大的数组是很常见的做法,但如果超大的数组被定义成局部变量,则很容易出现Runtime Error,解决办法也很简单:定义成全局变量即可。原因是局部变量分配在栈(较小),全局变量分配在堆(较大);

    

l  说明:这里所说的超大也不能无限制的大,可以根据题目的内存限制进行估算

3199 Hamming Problem为例

l  题目描述:For each three prime numbers p1, p2 and p3, let's define Hammingsequence Hi(p1, p2, p3), i=1, ... as containing in increasing order all thenatural numbers whose only prime divisors are p1, p2 or p3.

l  Forexample, H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27,...

l  So H5(2, 3,5)=6.

l  输出描述The output file must contain the single integer - Hi(p1, p2, p3). Allnumbers in input and output are less than10^18.

菜鸟之伤(21

l 典型错误——

l 没有仔细分析...

l 也不敢尝试...

l 直接被吓走了......

菜鸟之伤(21

l  总结:这个题目从本质上来说,和1058Humble Numbers是一样的,唯一吓人的就是数据范围的描述,可能会有人想: i 这么大,没法开数组呀?

l  但是,你仔细分析一下会发现:因为输出也是小于10^18,而同时,即使一组内的三个素数是最小的2,3,5,增长的速度也是很快的,所以不必为数组太大而着急。当然,也不必因为发现i很小而觉得数据太水,那是因为只能如此,不然输出就要超范围了~







字符串的输入

字符串的输入的主流函数:

一、scanf();  二、cin;  三、gets();  四、getline();          五、sscanf() 重点!!!!


一、scanf("%s",str);

遇见空格或换行就停止。

#include<stdio.h>
int main()
{
        char str[100];
        while(true)
        {
               scanf("%s",str);
               printf("%s\n",str);
        }
        return 0;
}
输入:123 456

输出:123

         456

 

二、cin>>str;与scanf();

相似遇见空格或换行就停止;以文件结束。

 

三、gets(str);

gets(str)函数与 scanf("%s",&str) 相似,但不完全相同,使用scanf("%s",&s) 函数输入字符串时存在一个问题,

就是如果输入了空格会认为字符串结束,空格后的字符将作为下一个输入项处理,但gets()函数将接收输入的整个字符串直到遇到换行为止或文件结束

 

四、getline(cin,str);

需要加头文件#include<stdlib.h> ;而且str 必须是 string类型;

读入一行以文件或换行结束。

 

五、sscanf();

1、sscanf与scanf类似,都是用于输入的,只是后者以键盘(stdin)为输入源,前者以固定字符串为输入源。

2、 %[a-z] 表示匹配a到z中任意字符,贪婪性(尽可能多的匹配)

  %[aB'] 匹配a、B、'中一员,贪婪性

  %[^a] 匹配非a的任意字符,贪婪性

3、用法例子

      a. 常见用法。

  char buf[512] ;

  sscanf("123456 ", "%s", buf);//此处buf是数组名,它的意思是将123456以%s的形式存入buf中!

  printf("%s\n", buf);

  结果为:123456

  b. 取指定长度的字符串。如在下例中,取最大长度为4字节的字符串。

  sscanf("123456 ", "%4s", buf);

  printf("%s\n", buf);

  结果为:1234

  c. 取到指定字符为止的字符串。如在下例中,取遇到空格为止字符串。

  sscanf("123456 abcdedf", "%[^ ]", buf);

  printf("%s\n", buf);

  结果为:123456

  d. 取仅包含指定字符集的字符串。如在下例中,取仅包含1到9和小写字母的字符串。

  sscanf("123456abcdedfBCDEF", "%[1-9a-z]", buf);

  printf("%s\n", buf);

     结果为:123456abcdedf

  当输入:

  sscanf("123456abcdedfBCDEF","%[1-9A-Z]",buf);

  printf("%s\n",buf);

   结果为:123456

  e. 取到指定字符集为止的字符串。如在下例中,取遇到大写字母为止的字符串。

   sscanf("123456abcdedfBCDEF", "%[^A-Z]", buf);

   printf("%s\n", buf);

   结果为:123456abcdedf 

  f、给定一个字符串iios/[email protected],获取 / 和 @ 之间的字符串,先将 "iios/"过滤掉,再将非'@'的一串内容送到buf中 

  sscanf("iios/[email protected]", "%*[^/]/%[^@]", buf);

  printf("%s\n", buf);

  结果为:12DDWDFF

  g、给定一个字符串"hello, world",仅保留world。(注意:","之后有一空格,%s遇空格停止,加 则是忽略第一个读到的字符串)

   sscanf("hello, world", "%*s%s", buf);

   printf("%s\n", buf);

   结果为:world

  %*s表示第一个匹配到的%s被过滤掉,即hello被过滤了

  如果没有空格则结果为NULL

 

  sscanf函数的用法

头文件 #include <stdio.h>

            定义函数 :  int sscanf (const char *str,const char * format,........);

            函数说明 :   sscanf()会将参数str的字符串根据参数format字符串来转换并格式化数据。格式转换形式请参考scanf()。转换后的结果存于对应的参数内。

            返回值 :  成功则返回参数数目,失败则返回-1,错误原因存于errno中。 返回0表示失败    否则,表示正确格式化数据的个数    例如:sscanf(str,"%d%d%s", &i,&i2, &s);    如果三个变成都读入成功会返回3。    如果只读入了第一个整数到i则会返回1。证明无法从str读入第二个整数。  

            范例

 #include <stdio.h>
   main() 
   { 
            int i; 
            unsigned int j; 
            char input[ ]=”10 0x1b aaaaaaaa bbbbbbbb”; 
            char s[5]; 
            sscanf(input,”%d %x %5[a-z] %*s %f”,&i,&j,s,s); 
            printf(“%d %d %s ”,i,j,s); 
   }
//输出: 10 27 aaaaa


            sscanf(stringBuf.c_str(), "%20[^#]#%20[^ ]",......)语句中""中的内容含义为:

            “%[ ]”符号用于声明字符串,它比“%s”更具体,可以用于设置读取的样式。例如“%[a-z]”只读取小写字母,读到其它字符就结束。注意,方括号中如果有“^”,代表一直读到某字符为止。例如:
            “%[^#]”:读取字符串,一直到出现“#”号为止。

            “%20[^#]”:读取20个字节的字符串,出现“#”号时结束。

            所以,“%20[^#]#%20[^ ]”的意义就是,

            读取两个20字节大小的字符串,第一个字符串可以用#结束,第二个字符串可以用回车符结束。

            它们的具体阐述,参见MSDN:“scanf Type Field Characters”章节,和“scanf Width  Specification”章节。

*********************************************************************************************************************************************

大家都知道sscanf是一个很好用的函数,利用它可以从字符串中取出整数、浮点数和字符串等等。它的使用方法简单,特别对于整数和浮点数来说。但新手可能并不知道处理字符串时的一些高级用法,这里做个简要说明吧。

1. 常见用法。

以下是引用片段:
  charstr[512]={0};
  sscanf("123456","%s",str);
  printf("str=%s",str);

  2. 取指定长度的字符串。如在下例中,取最大长度为4字节的字符串。

以下是引用片段:
  sscanf("123456","%4s",str);
  printf("str=%s",str);

  3. 取到指定字符为止的字符串。如在下例中,取遇到空格为止字符串。

以下是引用片段:
  sscanf("123456abcdedf","%[^]",str);
  printf("str=%s",str);

  4. 取仅包含指定字符集的字符串。如在下例中,取仅包含1到9和小写字母的字符串。

以下是引用片段:
  sscanf("123456abcdedfBCDEF","%[1-9a-z]",str);
  printf("str=%s",str);

  5. 取到指定字符集为止的字符串。如在下例中,取遇到大写字母为止的字符串。

以下是引用片段:
  sscanf("123456abcdedfBCDEF","%[^A-Z]",str);
  printf("str=%s",str);

*********************************************************************************************************************************************

名称: sscanf() - 从一个字符串中读进与指定格式相符的数据.

语法: int sscanf( string str, string fmt, mixed var1, mixed var2 ... );

整数 sscanf( 字符串 str, 字符串 fmt, 混合 var1, 混合 var2 ... );

用法: 以指定的格式 fmt 去解读字符串 str. fmt 中除了 %d 和 %s 以外, 亦可包含其他的字符串作为格式. 每一个 %d 或 %s 都对应一个参数, 按顺序为 var1, var2 ... %d 读入一个整数到参数中, 而 %s 读入一个字符串. * 亦可用于格式中, (即 %*d 和 %*s) 加了星号 (*) 表示跳过此数据不读入. (也就是不把此数据读入参数中) LPC 的 sscanf() 与 C 的 sscanf() 虽然相似, 但仍有不同之处. LPC 的 sscanf() 不需要 (也不可) 提供变量的内存位址给 sscanf(), 只需要给予变量的名字. 另一个不同点是, LPC 的 sscanf() 对于: sscanf( str, "%s %s", str1, str2 ); 的语法, 将会把 str 中的第一个英文单字 (即第一个空白字符以前的内容) 读入 str1, 后面其余的内容读入 str2.

sscanf() 会返回符合格式的 %d 和 %s 总数.

以前曾经编写过这样的小程序:一个文本文件,每行是一条记录,每条记录中包含多个字段,每个字段之间以某种定界符分开,举例如下:

Notebook,IBM,ThinkPad X32,6,12000

(各字段以逗号分隔,内容依次是:物品名称,生产厂家,型号,数量,价格)

如果要对这样的一行记录进行处理,提取出各个字段,怎么做比较好呢?

我以前的做法是在一个循环中用strtok函数每次取一个字段,然后将内容保存到一个字符串数组中。这样做虽然可行,但我总感觉写出的代码有些啰嗦。

最近看到一段代码,用C的标准库函数sscanf,处理这样的数据,只需一行就可以了。我把代码整理了一下,去掉了无关的部分,核心部分如下:

float price;
int quantity;
char category[21], name[21];
char vendor[21], sku[21];
char buf[201];
fp = fopen(filename, "r");
fgets(buf, 200, fp);
sscanf(buf,"%20[^#]#%20[^#]#%f#%i#%20[^#]#%20[^\n]",name, sku, &price, &quantity, category, vendor);


下面简单做些解说:

%20[^#]# 最多读入20个字符,直到遇见定界符#,但不包含定界符

%f# 读入一个浮点数,直到遇见定界符#

%i# 读入一个整数,直到遇见定界符#

%20[^\n] 最多读入20个字符,忽略行尾的回车符

是不是很简洁明了呢?

#include <stdio.h>
int main()
{

char log[]="<14>2002-11-11 12:12:12 11.22.33.44 3 3 aaaa aaaaaa";
//char log[]="<1>2002-11-11 12:12:12 11.22.33.44 3 aaaa aaaaaa";
char test[]="<1111> 22";
char log2[200];
char str1[20],str2[20],str3[20],str4[20],str5[20],str6[20],char str7[20];
int a1,a2,a3,a4,a5,a6;
sscanf(log,"<%d>%s %s %s %d %d %s",&a1,str2,str3,str4,&a5,&a6,str7);
printf("%d\n",a1);
printf("%s\n",str2);
printf("%s\n",str3);
printf("%s\n",str4);
printf("%d\n",a5);
printf("%d\n",a6);
printf("%s\n",str7);
sscanf(test,"<%d> %d",&a5,&a6);
printf("%d\n",a5);
printf("%d\n",a6);
sscanf(log,"<%[^>]>%[^ ] %[^ ] %[^ ] %[^ ] %[^ ] %[^$]",str1,str2,str3,str4,str5,str6,str7);
printf("%s\n",str1);
printf("%s\n",str2);
printf("%s\n",str3);
printf("%s\n",str4);
printf("%s\n",str5);
printf("%s\n",str6);
printf("%s\n",str7);
return 1;

}


const char *str = "drw-rw-rw- 1 user group 0 Oct 28 2003";

上面是源串,我要分别得到drw-rw-rw-,group字段

注意:因为这几个字段的值会变化,所以我要用格式化输入,分别存入下面的a b c中,高手帮忙!

下面这个是我没成功的尝试

char a[20];
char b[50];
char c[20];
//int ret = sscanf(str, "%[^'' '']* %[''u''] %[^'' '']", a, b, c);
int ret = sscanf(str, "%s%*s%*s%s%*s%*s%*s%*s%s", a, b, c);



这样就可以了,不要的东西都抛弃掉了



今天看到一个奇怪的scanf。其实这只是用了正则表达式。

sscanf(user, "%127[^:]:%127[^ ]", user_name, password);

"%127[^:]:%127[^ ]",是正则表达式

用scanf或者printf,可以在%后面跟%d,%s等东西,也可以跟一个正则表达式。

这里,127表示最多可以接受127个字符,[^:]是正则表达式,表示非":",到":"结束

后面,%127[^ ],同样,其中[^ ]是正则表达式,表示非" ",到" "结束

所以,如果user是"wpc:123456"的字符串,那么经过上面的sscanf后,

user_name是wpc,而password是123456

 

树状数组

       一个数组很大的时候,几项求和(不一定求和,求和最常见),累加就显得太耗时了,时间复杂度为O(n),并且采用累加的方法还有一个局限,那就是,当修改掉数组中的元素后,仍然要你求数组中某段元素的和,就显得麻烦了。所以我们就要用到树状数组,时间复杂度为O(lgn),相比之下就快得多

         树状数组图:

        

c1=a1,c2=a1+a2,c3=a3,c4=a1+a2+a3+a4,c5=a5,c6=a5+a6,c7=a7,c8=a1+a2+a3+a4+a5+a6+a7+a8,c9=a9,c10=a9+a10,c11=a11........c16=a1+a2+a3+a4+a5+.......+a16。

      分析上面的几组式子可知:

    1. 当 i 为奇数时,ci=ai ;
    2. 当 i 为偶数时,就要看 i 的因子中最多有二的多少次幂,例如,6 的因子中有 2 的一次幂,等于 2 ,所以 c6=a5+a6(由六向前数两个数的和),4 的因子中有 2 的两次幂,等于 4 ,所以 c4=a1+a2+a3+a4(由四向前数四个数的和)。

        有公式:cn =  a(n-2^k+1)+.........+an(其中 k 为 n 的二进制表示中从右往左数的 0 的个数,2^k则是n的因子中最大的2的次幂)。

         那么,如何求 2^k 呢?求法如下:

int lowbit(int i)
{  // 返回i的因子中含有 2的最大幂,如6的因子中最大2的幂是2^1 = 2 ,8的因子最大2次幂 2^3 = 8;
	return i&(-i);
}

lowbit()的返回值就是 2^k 次方的值。

 

(一)创建树状数组

for(i=1;i<=n;i++)
	{
		scanf("%d",&e);
		a[i] = e;
		if(i&1)//奇数,树状数组与原始位置数据一样
			Tree_a[i] = a[i];
		else //偶数,树状数组对应位置存的为几项的和
		{
			int sum = 0;
			for(j=i+1-lowbit(i);j<=i;j++)	sum += a[j];//求出从a[i]与前 lowbit(i) 项的和
			Tree_a[i] = sum;
		}
	}//建好树状数组Tree_a[] ,  原始数组a[]


(二)当数组中的元素有变更时,树状数组就发挥它的优势了,算法如下(修改为给某个节点x加上 y,数组长度n ):

        

void change(int x, int y,int n)
{//给x位置增加y,则x到n之间需要调整
	while(x<=n)
	{
		Tree_a[x] += y;
		x += lowbit(x);//只调整个别的
	}
}


(三)求x到y之间的数据的和(根据数组数组求)

SUM = f_sum(y) - f_sum(x-1);

int f_sum(int x)
{//返回前x个数的和
	if(x==0) return 0;
	int sum = 0;
	while( x>0 )
	{
		sum += Tree_a[x]; //求前x数的和
		x -= lowbit(x);
	}
	return sum;
}


 

Hello World

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server