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

7-4 Load Balancing (30 分)

负载均衡（Load balancing） 是一种在后端服务器群组中精确分配入网流量的方法。一种负载均衡算法采用精确的路由策略进行负载分配。

If we can be capable of estimating the maximum incoming traffic load, there exists an algorithm that operates on the basis of the following rule.

• The incoming traffic load of size S can initially be divided into two parts, which could further each be subdivided into smaller sections.
• The process ensures that only one partition occurs at any given time.
• At all times, the minimum load must remain more than half the maximum load.
• Every size is a positive integer.
• The process continues until no further partitions can occur.

Once decomposition concludes for this stage (at which point), only three servers are needed to accommodate the respective load levels of three units for one server and two units each for the other two servers.

Your task involves determining the optimal number of backend servers needed for this algorithm. However, because different partitions might exist, it's essential to identify an optimal solution where the disparity between the largest and smallest server counts is as small as possible.

Input Specification:

Each input file includes a single test instance, which provides a positive integer S (where 2≤N≤200), representing the volume of incoming traffic.

Output Specification:

For each case, two numbers are printed in a line specifically indicating M as the maximum number of backend servers needed and D as well as representing the minimal difference between partition sizes when using M servers. Additionally, these two values must be printed with single spaces separating them to ensure no leading or trailing spaces on any line.

Sample Input:

    22
    
    AI写代码

结尾无空行

Sample Output:

    4 1
    
    AI写代码

结尾无空行

Hint:

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

 22

    
 = 8 + 14
    
 = 8 + 7 + 7
    
 = 4 + 4 + 7 + 7
    
    
    
    
    AI写代码

or

 22

    
 = 10 + 12
    
 = 10 + 6 + 6
    
 = 4 + 6 + 6 + 6
    
    
    
    
    AI写代码

or

 22

    
 = 10 + 12
    
 = 10 + 6 + 6
    
 = 5 + 5 + 6 + 6
    
    
    
    
    AI写代码

All four servers are required for this task. The minimal difference in the final partition is computed as six minus five, resulting in a value of one.

解读：将代码放置此处或许是个好主意。
等有时间时再进行深入解读。
大致可以用深度优先搜索来解决。
如今陈姥姥对这类深度搜索问题愈发青睐。
哎呀！真是如此。

如果你难以承受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);
    
 }
    
    
    
    
    AI写代码