Greedy algorithm problem solving

A. Base station installation

Description

Once upon a time, there was an endless beach. Behind the beach was land and in front of it was a vast sea. There are many small islands in the sea. Now, some base stations (anywhere on the beach) need to be installed on the beach, so that the residents on the island can talk with their mobile phones. The coverage distance of all base stations is d, and the island within the distance d can receive the signal sent by the base station.

We use the Cartesian coordinate system to express this problem. We define the x-axis as the beach. Above the x-axis is the sea and below it is the land. Now give the location of each island (expressed in x-y coordinates) and the coverage d of the base station. Your task is to write a program to calculate how many base stations need to be installed on the beach to cover all the islands?

Input

The input contains multiple sets of data. For each group of data, the first row contains two integers n (1 < = n < = 1000) and D, where n represents the number of islands and D represents the coverage distance of the base station. Next, there are n rows, each containing two integers, representing the location coordinates of the island. Exit when n = 0 and d = 0 are entered.

Output

For each group of data, the output includes the number of data groups, such as sample, followed by the minimum number of base stations to be installed. If there is no solution, output - 1.

Sample Input

3 2
1 2
-3 1
2 1
1 2
0 2
1 -2
0 2
0 0

Sample Output

Case 1: 2
Case 2: 1
Case 3: -1

Answer

#include <bits/stdc++.h>
using namespace std;

#define MAX 1001
struct TPoint {
	int x;
	int y;
};
struct TLimit {
	double dFrom;
	double dTo;
};
TPoint tIsland[MAX];
TLimit tSeg[MAX];
void vInput(int nN);
bool bcheck(int nN,int nD);
void vOut(int nC,int nOut);
void vSort(int nN);
bool bCmp(const TLimit &tA,const TLimit &tB);
int nGetAns(int nN);
int main() {
	int nCase;
	int nAns;
	int nLands,nDist;
	nCase=1;
	while(cin>>nLands>>nDist) {
		if((0==nLands)&&(0==nDist)) {
			return 0;
		} else {
			vInput(nLands);
			if(bcheck(nLands,nDist)) {
				vSort(nLands);
				nAns=nGetAns(nLands);
			} else {
				nAns=-1;
			}
			vOut(nCase,nAns);
			nCase++;
		}
	}
	return 0;
}
void vInput(int nN) {
	int i;
	for(i=1; i<=nN; i++) {
		cin>>tIsland[i].x>>tIsland[i].y;
	}
}
bool bcheck(int nN,int nD) {
	int i;
	for(i=1; i<=nN; i++) {
		if(tIsland[i].y>nD) {
			return false;
		}
		tSeg[i].dFrom=tIsland[i].x-sqrt(1.0*nD*nD-1.0*tIsland[i].y*tIsland[i].y);
		tSeg[i].dTo=tIsland[i].x+sqrt(1.0*nD*nD-1.0*tIsland[i].y*tIsland[i].y);
	}
	return true;
}
void vOut(int nC,int nOut) {
	cout << "Case " << nC << ": " << nOut << endl;
}
void vSort(int nN) {
	sort(&tSeg[1],&tSeg[nN+1],bCmp);
}
bool bCmp(const TLimit &tA,const TLimit &tB) {
	return (tA.dFrom<tB.dFrom);
}
int nGetAns(int nN) {
	int nRet;
	int i;
	double dTemp;
	nRet=1;
	dTemp=tSeg[1].dTo;
	for(i=2; i<=nN; i++) {
		if(tSeg[i].dFrom>dTemp) {
			nRet++;
			dTemp=tSeg[i].dTo;
		} else {
			if(dTemp>tSeg[i].dTo) {
				dTemp=tSeg[i].dTo;
			}
		}
	}
	return nRet;
}

B. Packaging problem

Description

A factory packs its products in square boxes with a size of 1 × 1,2 × 2,3 × 3,4 × 4,5 × 5,6 × Six kinds, height h. The products are always bundled into 6 with a height of h × 6 package boxes are delivered to the customer, because the customer hopes that the fewer package boxes the better. Please write a program to calculate the minimum number of parcel boxes needed to deliver the products purchased by customers.

Input

The input contains multiple sets of data. Each group of data has a row containing 6 integers separated by spaces, representing 1 respectively × 1 new products, 2 × 2 products...... 6 × 6. Number of products. Exit when 6 zeros are entered.

Output

Output one line for each group of data, and output the minimum number of package boxes required.

Sample Input

0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0

Sample Output

2
1

Answer

#include <bits/stdc++.h>
using namespace std;

int nBox[7];
int nBigBox;
void vInit();
void vPack();
void vOut();
void vInput();
int main() {
	int nSum;
	vInput();
	nSum=nBox[6]+nBox[5]+nBox[4]+nBox[3]+nBox[2]+nBox[1];
	while(nSum!=0) {
		vInit();
		vPack();
		vOut();
		vInput();
		nSum=nBox[6]+nBox[5]+nBox[4]+nBox[3]+nBox[2]+nBox[1];
	}
	return 0;
}
void vInit() {
	nBigBox=0;
}
void vPack() {
	int n1X1,n2X2;
	int nTemp;
	n1X1=0;
	n2X2=0;
	nBigBox+=nBox[6];
	nBigBox+=nBox[5];
	nBigBox+=nBox[4];
	n2X2+=nBox[4]*5;
	nBigBox+=nBox[3]/4;
	nTemp=nBox[3]%4;
	if(nTemp>0) {
		nBigBox++;
		switch(nTemp) {
			case 1:
				n2X2+=5;
				break;
			case 2:
				n2X2+=3;
				break;
			case 3:
				n2X2+=1;
				break;
		}
	}
	if(nBox[2]>n2X2) {
		nBigBox+=(nBox[2]-n2X2)/9;
		nTemp=(nBox[2]-n2X2)%9;
		if(nTemp>0) {
			nBigBox++;
		}
	}
	n1X1=nBigBox*36-nBox[6]*36-nBox[5]*25-nBox[4]*16-nBox[3]*9-nBox[2]*4;
	if(nBox[1]>n1X1) {
		nBigBox+=(nBox[1]-n1X1)/36;
		nTemp=(nBox[1]-n1X1)%36;
		if(nTemp>0) {
			nBigBox++;
		}
	}
}
void vOut() {
	cout << nBigBox << endl;
}
void vInput() {
	int i;
	for(i=1; i<=6; i++) {
		cin >> nBox[i];
	}
}

C. Class questions

Description

Many graduate students of Peking University live in Wanliu campus. They go to Yanyuan, which is 4.5 kilometers away, by bus or bike every day. Because the traffic in Beijing is terrible (I think it's also terrible), many students choose to ride to class. Charlie's cycling habits are different from those of other students. Other students ride at a fixed speed, while Charlie is with a mm, so he won't feel bored. When Charlie sets out, he will find a mm to accompany him to Yanyuan. If he finds PLMM, he will be with her, otherwise he will continue to look for it. On the way to Yanyuan, if a mm is faster and surpasses him, he will leave the mm around him to catch up with the faster mm, and then go to Yanyuan with her. Let's assume that Charlie's departure time is 0. Now we give a lot of MM's departure time and speed. When can Charlie get to Yanyuan?

Input

Contains multiple sets of data. The first row of each group of data is represented by an integer N (1 < = N < = 10000), which represents the number of MM. When N=0, it exits. Next, there are N rows, and each row represents the riding information of a MM. Format: Vi, Ti. 0 < Vi < = 40 represents the cycling speed (km/h), Ti is the departure time (s) of the MM, and Ti may be less than 0.

Output

Each row of output represents a set of data. Output the time when Charlie arrives at Yanyuan. If it is less than 1 second, it shall be calculated as 1 second.

Sample Input

4
20 0
25 -155
27 190
30 240
2
21 0
22 34
0

Sample Output

780
771

Answer

#include <bits/stdc++.h>
using namespace std;

int nTime[10005];
int nNowTime;
int nInput(int nN);
void vSort(int nN);
void vOut(int nN);
int main() {
	int nNum,nCnt;
	cin>>nNum;
	while(nNum != 0) {
		nCnt = nInput(nNum);
		vSort(nCnt);
		vOut(nCnt);
		cin>>nNum;
	}
	return 0;
}
int nInput(int nN) {
	double dTime;
	int nV,nT,nCnt=0,nArrive;
	for(int i=0; i<nN; i++) {
		cin>>nV>>nT;
		if(nT<0) {
			continue;
		} else {
			dTime = (double) 4500/nV/1000*3600;
			nArrive = ceil(dTime)+nT;
			nTime[nCnt++] = nArrive;
		}
	}
	return nCnt;
}
void vSort(int nN) {
	sort(nTime,nTime+nN);
}
void vOut(int nN) {
	cout<<nTime[0]<<endl;
}

D. Highway maintenance problems

Description

In recent decades, China's expressways have developed rapidly, and the mileage of expressways covering the whole country has increased year by year. Due to the fast construction speed, it has also brought a problem, that is, the construction quality of expressways is worrying, but not all problems are caused by the construction quality on the one hand. Long-term overload and overrun operation will also cause damage to the subgrade and pavement. We often see potholes on the pavement of some sections, Once there is a problem on the pavement, it is likely to cause serious traffic accidents, so it needs to be repaired. The repair of expressway has many particularity. For example, a small pothole is not enough to be repaired. It is necessary to dig out and re lay materials in a section near the pothole, even if there is only one small pothole, and even the repair cost of a small pothole is the same as that of many connected potholes. Now we calculate a minimum repair length as a repair unit. Within this length range, the repair cost of a depression and multiple depressions is the same. Now we give you the location of all depressions on a highway (we assume that the starting point is one end of the highway and the other end is long enough). Please write a program to calculate the minimum number of repair units needed to repair all depressions.

Input

There are multiple groups of test data in this problem, and each group of data has two lines. The first line has two integers n and l (separated by spaces), which respectively represent the length L of n (0 < = n < = 1000) depressions and repair units (0 < l < = 100). The second line contains n integers a1,a2... an (separated by spaces), representing the positions of N depressions (0 < = AI < = 20000).

Output

For each set of input, there is only one line of output, that is, the minimum number of repair units required.

Sample Input

2 50
10 61
4 50
10 59 60 61

Sample Output

2
2

Answer

#include <bits/stdc++.h>
using namespace std;

int nIndex[10001];
void vInput(int nN);
void vSort(int nN);
int nCount(int nN,int nL);

int main() {
	int nRet;
	int nNum,nLen;
	while(cin>>nNum>>nLen) {
		if(nNum == 0) {
			cout<<0<<endl;
			continue;
		}
		vInput(nNum);
		vSort(nNum);
		nRet = nCount(nNum,nLen);
		cout<<nRet<<endl;
	}

	return 0;
}

void vInput(int nN) {
	for(int i=0; i<nN; i++) {
		cin>>nIndex[i];
	}
}
void vSort(int nN) {
	sort(nIndex,nIndex+nN);
}
int nCount(int nN,int nL) {
	int nRet,nTemp;
	nTemp = nIndex[0]+nL;
	nRet=1;
	for(int i=1; i<nN; i++) {
		if(nIndex[i]>nTemp) {
			nRet++;
			nTemp = nIndex[i]+nL;
		}
	}
	return nRet;
}

Tags: C++ Algorithm

Posted by seularts on Sun, 08 May 2022 10:19:18 +0300