浙江大学计算机与软件学院2021年考研复试上机7-4 Load Balancing (30 分)_浙江大学 负载均衡

7-4 Load Balancing (30 分)

Load balancing (负载均衡) refers to efficiently distributing incoming network traffic across a group of backend servers. A load balancing algorithm distributes loads in a specific way.

If we can estimate the maximum incoming traffic load, here is an algorithm that works according to the following rule:

• The incoming traffic load of size S will first be partitioned into two parts, and each part may be again partitioned into two parts, and so on.
• Only one partition is made at a time.
• At any time, the size of the smallest load must be strictly greater than half of the size of the largest load.
• All the sizes are positive integers.
• This partition process goes on until it is impossible to make any further partition.

For example, if S=7, then we can break it into 3+4 first, then continue as 4=2+2. The process stops at requiring three servers, holding loads 3, 2, and 2.

Your job is to decide the maximum number of backend servers required by this algorithm. Since such kind of partitions may not be unique, find the best solution -- that is, the difference between the largest and the smallest sizes is minimized.

Input Specification:

Each input file contains one test case, which gives a positive integer S (2≤N≤200), the size of the incoming traffic load.

Output Specification:

For each case, print two numbers in a line, namely, M, the maximum number of backend servers required, and D, the minimum of the difference between the largest and the smallest sizes in a partition with M servers. The numbers in a line must be separated by one space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

22

结尾无空行

Sample Output:

4 1

结尾无空行

Hint:

There are more than one way to partition the load. For example:

22
= 8 + 14
= 8 + 7 + 7
= 4 + 4 + 7 + 7

or

22
= 10 + 12
= 10 + 6 + 6
= 4 + 6 + 6 + 6

or

22
= 10 + 12
= 10 + 6 + 6
= 5 + 5 + 6 + 6

All requires 4 servers. The last partition has the smallest difference 6−5=1, hence 1 is printed out.

解析：先把代码放在这吧，以后有心情了来写解析，大概就是用一下深度优先搜索就可以解决了，现在陈姥姥越来越喜欢出这种深搜的题了。哎，要命。

如果你刷PAT刷到快崩溃了，希望你能坚持下去不要放弃，胜利的曙光即将到来，与你共勉！

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
 
vector<int> arr;
int maxS; 
int minDiff;
void dfs()
{
	bool flag=false;
	vector<int> arr1;
	arr1 = arr;
	sort(arr.begin(),arr.end());
	int now = arr[arr.size()-1];
	for(int i=1; i<=now/2; i++){
		int a,b;
		if(arr.size()>=2){
			a=min(i,arr[0]);
		}else a = i;
		if(arr.size()>=2){
			b=max(now-i,arr[arr.size()-2]);
		}
		else b=now-i;
		if(a*1.0>b*1.0/2){
			flag=true;
			arr=arr1;
			sort(arr.begin(),arr.end());
			arr.pop_back();
			arr.push_back(i);
			arr.push_back(now-i);
			dfs();
			arr = arr1;
		}
	}
	if(flag==false){
		int a = arr.size();
		if(a>maxS){
			maxS = arr.size();
			minDiff = arr[arr.size()-1]-arr[0];
		}
		else if(a==maxS){
			if(arr[arr.size()-1]-arr[0]<minDiff){
				minDiff = arr[arr.size()-1]-arr[0];
			}
		}
	}
} 
 
int main()
{
	int S;
	scanf("%d",&S);
	arr.push_back(S);
	maxS = -1;
	minDiff = 1000000000; 
	dfs();
	printf("%d %d\n",maxS,minDiff);
}