Zcmu--1052: holedox eating (C language)

Description

Holedox is a small animal which can be considered as one point. It lives in a straight pipe whose length is L. Holedox can only move along the pipe. Cakes may appear anywhere in the pipe, from time to time. When Holedox wants to eat cakes, it always goes to the nearest one and eats it. If there are many pieces of cake in different directions Holedox can choose, Holedox will choose one in the direction which is the direction of its last movement. If there are no cakes present, Holedox just stays where it is.

Input

The input consists of several test cases. The first line of the input contains a single integer T (1 <= T <= 10), the number of test cases, followed by the input data for each test case.The first line of each case contains two integers L,n(1<=L,n<=100000), representing the length of the pipe, and the number of events.

The next n lines, each line describes an event. 0 x(0<=x<=L, x is a integer) represents a piece of cake appears in the x position; 1 represent Holedox wants to eat a cake.

In each case, Holedox always starts off at the position 0.

Output

Output the total distance Holedox will move. Holedox don’t need to return to the position 0.

Sample Input

3

10  8

0  1

0  5

1

0  2

0  0

1

1

1

10  7

0  1

0  5

1

0  2

0  0

1  1

10  8

0  1

0  1

0  5

1

0  2

0  0

1

1

Sample Output

Case 1: 9

Case 2: 4

Case 3: 2

analysis ： Note that there is no upper limit to the amount of food in each location , Then we look for the position of the food on the left and right every time , Go wherever you are near , Then, if it is the same, it is necessary to judge the last movement direction to decide whether to go to the right or the left , We use... Every time we exercise f Just record the direction .

#include <stdio.h>
int a[100005]; // Used to record the amount of food at each coordinate point  
int main()
{
	int t,l,q,s,x,f,z,i,s1,s2,y1,y2,p,c=0;
	scanf("%d",&t);
	while(t--){
		c++;		// Test case number  
		scanf("%d%d",&l,&q);
		for(i=0;i<=l;i++) a[i]=0;	// initialization 0 
		x=0,f=1,s=0;	//x Represents the current location ,f Represents the last direction (1 For the right ,-1 To the left ),s Represents the total moving distance  
		while(q--){
			scanf("%d",&z);
			if(z==0){ 
				scanf("%d",&p);
				a[p]++;		// Number of food in corresponding position +1 
			}else{
				s1=0,s2=0;	//s1,s2 On behalf of the protagonist   On the right   On the left   Is there any food  
				for(i=x;i<=l;i++){	// Look for the right side first  
					if(a[i]>=1){	// If there is  
						y1=i;		//y1 Record the current food location  
						s1=1;		//s1 There is food on the right  
						break;
					}
				}
				for(i=x-1;i>=0;i--){	// Look for the left  
					if(a[i]>=1){
						y2=i;
						s2=1;
						break;
					}
				}
				if(s1*s2==0){	// Multiply by 0 It means there is no food on either side , Or on the left , Or on the right  
					if(s1==1){	// On the right  
						s+=y1-x;	// Cumulative distance  
						a[y1]--;	// Quantity of food at this location -1 
						x=y1;		// Update the current lead position  
						f=1;		// The direction is right  
					}
					else{		// On the left  
						s+=x-y2;
						x=y2;
						a[y2]--;
						f=-1;	// The direction is left  
					}  
				}else{			// This is the case for both sides , To compare distances  
					if(y1-x<x-y2){		// Right near  
						s+=y1-x;
						x=y1;
						a[y1]--;
						f=1;
					}else if(y1-x>x-y2){	// Left near  
						s+=x-y2;
						x=y2;
						a[y2]--;
						f=-1;
					}else{			// As close as , according to f To determine whether to go to the left or the right  
						if(f==1) s+=y1-x,x=y1,a[y1]--;
						else s+=x-y2,x=y2,a[y2]--;
					}
				}
			}
		}
		printf("Case %d: %d\n",c,s);
	}
	return 0;
}