首页 > 试题广场 >

信服机柜

[编程题]信服机柜
  • 热度指数:445 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

深信服的设备通常是叠放在机架上的。设备(水平放置)有1U,2U两种高度,2U的高度是1U的两倍。对于一个高度为h的机架,可以叠放多台设备,只要这些设备总高度不超过h就可以。1U、2U两种型号的设备和机架的宽度相等,而且为了避免损坏,必须水平放置设备,而不允许将设备竖直放置。

 

客户买了一批深信服设备,其中1U设备有a台,2U设备有b台。现在他想知道,需要多个高度为h的机架,才能全部放下这批设备?

 

    注:每个机架都可以随意叠放1U和2U的设备,只要总高度不超过h就行,对设备的叠放顺序和数量搭配没有要求。但是不同的叠放策略对于机柜数量的需求是不一样的。比如某客户有2台1U设备和2台2U设备,当使用h=3的机架时,他可以每个机架上放一台1U和一台2U设备,这样总共两个机架就够用了。但如果执意要把两台1U设备叠放在一起,则至少需要3个机架才够用。这里我们假设客户总是按照最好的策略来叠放这些设备。


输入描述:
第一行一个正整数T(T<=100),表示有T个客户购买了深信服的设备。

接下来T行,每行三个整数a,b,h。(0<=a,b<=100000,2<=h<=100000)

表示这个客户1U设备有a台,2U设备有b台,他所用的机架高度为h。


输出描述:
输出T行,每行一个正整数,表示该客户最少需要的机架数量。
示例1

输入

2
2 2 3
0 10 5

输出

2
5
#include<iostream>
#include<vector>
using namespace std;
    
int main(){
    int t;
    cin>>t;
    vector<int> a,b,h;
    int temp1,temp2,temp3;
    for(int i = 0; i < t; i++) {
        cin >> temp1;
        a.push_back(temp1);
        cin >> temp2;
        b.push_back(temp2);
        cin >> temp3;
        h.push_back(temp3);
    }
    for(int i = 0; i < t; i++) { // 循环计算每个客户的情况
        int flag = (((h[i]) % (2))== 0 ? 0 : 1); // 当前机架高度是否为奇数
        int doubleFit = h[i] / 2; // 每个机架最多能放多少个2U
        int remain = h[i] - (b[i] % doubleFit) * 2; // 把2U全部放完后最后一个机架还有多少空间
        int total = ((b[i] % doubleFit) || b[i] < doubleFit)? b[i] / doubleFit + 1 : b[i] / doubleFit;  // 定义总数,初始化为2U放完所需机架
        if(flag) { // 如果是奇数
            if(a[i] <= (remain + total - 1)) { // 如果1U的数量小于等于最后一个货架剩余空间
                cout << total << endl; // 输出结果
            }
            else { // 如果1U的数量大于最后一个货架剩余空间
                total = (((a[i] - remain - total + 1) % h[i]) || ((a[i] - remain - total + 1) < h[i]))?total + (a[i] - remain - total + 1) / h[i] + 1:total + (a[i] - remain - total + 1) / h[i]; // 总数增加去除剩余空间数量后的1U所需机架数量
                cout << total << endl; // 输出结果
            }
        }
        else {
            if(a[i] <= remain) { // 如果1U的数量小于等于最后一个货架剩余空间
                cout << total << endl; // 输出结果
            }
            else { // 如果1U的数量大于最后一个货架剩余空间
                total = (((a[i] - remain) / h[i]) || (a[i]-remain < h[i])) ? total + (a[i] - remain) / h[i] + 1: total + (a[i] - remain) / h[i]; // 总数增加去除剩余空间数量后的1U所需机架数量
                cout << total << endl; // 输出结果
            }
        }
    }
    return 0;
}

发表于 2021-08-30 20:21:39 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int times;
    cin >> times;
    while(times--)
    {
     int a, b, h;
		cin >> a >> b >> h;
		int thish = h;//每轮重新开一个货架
		int total = 0;
		while (a > 0 || b > 0)
		{
			if (b > 0)//尽可能的用b填满货架
			{
				int choose_b = thish / 2;
                if(b - choose_b >0)
                {
                thish -= 2 * choose_b;
				b -= choose_b;
                }
                else {
                thish -= 2 * b;
				b  = 0;
                }
				
			}
			if (a > 0 && thish > 0)//货架不满 再次填充
				a -= thish;
			
			thish = h;
			total++;//每次循环用一个货架
		}
		cout << total << "\n";
    }
    
}

发表于 2023-09-20 16:18:45 回复(0)
贪心就好
发表于 2022-12-25 15:11:50 回复(0)
利用队列可以很快得出答案。
思路就是分h分,奇偶先装2u的,2u装完之后利用1u将空格补满,在将多余的1u装上
#include<iostream>
#include<queue>
using namespace std;
int main() {
	int T;
	cin >> T;
	queue<int> queue_a, queue_b, queue_h;   //队列表示a数量u,b数量2u,以及高度h。
		for (int i = 0; i < T; i++) {
			int a, b, h;
			cin >> a >> b >> h;
			queue_a.push(a);
			queue_b.push(b);
			queue_h.push(h);
		}
	while (!queue_h.empty()) {
		int a, b, h;
		a = queue_a.front();
		b = queue_b.front();
		h = queue_h.front();
		queue_a.pop();
		queue_h.pop();
		queue_b.pop();
		if (h % 2 == 0 ? 1 : 0) {
			b = b + a / 2;
			int result = b / (h / 2);
			if (b % (h / 2) != 0) {
				result++;
			}
			if (a % 2 != 0 && b % (h / 2) == 0) {
				result++;
			}
			cout << result << endl;
		}
		else {
			int h1 = h-1;
			int result = b / (h1 / 2);
			int remind = result;
			if (b % (h1 / 2) != 0) {
				result++;
				remind += h - 2 * (b % (h1 / 2));
			}
			if (a <= remind)
				cout << result << endl;
			else {
				a = a - remind;
				result += a / h + (a%h == 0 ? 0 : 1);
				cout << result << endl;
			}
		}
	}
}



发表于 2022-03-01 16:43:05 回复(0)
def smallest_num_of_machine(a,b,h):
    if h&1==1:
        flag,ex_b=divmod(b,h//2)
        if ex_b!=0:
            if a<=flag+h-2*ex_b:
                return flag+1
            else:
                return flag+1-(-(a-(flag+h-2*ex_b))//h) # -(-a//b) 向上取整
        else:
            if a<=flag:
                return flag
            else:
                return flag-(-(a-flag)//h)
    else:
        flag, ex_b = divmod(b, h // 2)
        if ex_b!=0:
            if a<=h-2*ex_b:
                return flag+1
            else:
                return flag+1-(-(a-(h-2*ex_b))//h)


if __name__=='__main__':
    a,b,h=map(int, input().split())
    print(smallest_num_of_machine(a,b,h))

发表于 2020-08-26 20:08:50 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin>>T;
    for(int i=0;i<T;i++)
    {
        int a,b,h;
        cin>>a>>b>>h;
        int num2perh=h/2;
        int mod=h%2;
        int num2shell=b/num2perh;
        int lessnum2=0;
        if(b%num2perh!=0)
            lessnum2=b%num2perh;
        int num1cur=a-mod*num2shell-(h-2*lessnum2);
        if(lessnum2>0)
            num2shell++;
        if(num1cur>0)
        {
            if(num1cur%h!=0)
                num2shell++;
            num2shell+=(num1cur/h);
        }
        cout<<num2shell<<endl;
    }
}

发表于 2020-08-25 11:25:10 回复(0)