简单解题思路

核心问题

给定多个团队的任务处理能力参数，计算每个团队完成n个任务的最优耗时，并按性能排序输出。

算法流程

1. 输入处理

• 读取测试用例数T
• 对每个测试用例：
  • 读取n（总任务数）、m（最小分组数）、l（团队数）
  • 读取每个团队的名称和效率参数（a:直接处理系数，b:拆分成本）

2. 耗时计算

• 对每个团队：
  • 初始化剩余任务数rw=n，总耗时hf=0
  • 循环判断拆分条件：
    • 当剩余任务可分(rw/2≥m)且拆分更划算(拆分成本b≤拆分后处理耗时差)
    • 执行拆分：rw减半，hf增加拆分成本b
  • 最后加上直接处理剩余任务的耗时(rw-m)*a

3. 结果排序

• 按总耗时升序排序
• 耗时相同时按团队名称字典序排序

4. 输出结果

• 按格式输出各团队名称和计算耗时

关键点

• 贪心策略：每次拆分都选择当前最优的决策
• 终止条件：当无法继续拆分或拆分不再节省时间时停止
• 复杂度控制：通过数学计算替代真实拆分操作，保证高效性

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;
struct nod{
	string s;
	int num;
}da[100010];
bool cmp(nod a, nod b)
{
	if(a.num==b.num)
	{
		return a.s<b.s;
	}else
	{
		return a.num<b.num;
	}
}
int main()
{
	int T;
	cin>>T;
	int tag=0;
	while(T--)
	{
		tag++;
		int n,m,l;
		cin>>n>>m>>l;
		for(int i=0;i<l;i++)
		{
			string t;
			cin>>t;
			for(int j=0;j<t.size();j++)
			{
				if(t[j]==':'||t[j]==',')
				{
					t[j]=' ';
				}
			}
			istringstream iss(t);
			int a,b;	
			iss>>da[i].s>>a>>b;
			int rw=n;
			int hf=0;
			//博友程序while(u/2>=m&&(u-u/2)*a>=b)    	while((rw/2)>=m && (rw/2)*a>b) 也ac 
			while((rw/2)>=m && (rw/2)*a>=b) 
			{
				rw=rw/2;
				hf=hf+b;
			}
			hf=hf+(rw-m)*a;
			da[i].num=hf; 
		}
		sort(da,da+l,cmp);
		cout<<"Case "<<tag<<endl;
		for(int i=0;i<l;i++)
		{
			cout<<da[i].s<<" "<<da[i].num<<endl;
		}
	} 
	return 0;
}