{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003e杰克帮助他的导师构建了一个简单的分布式存储系统。他使用多台服务器并将它们连接成以下拓扑结构:\u003c/p\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/3448936235eb4f63d1cb19e3bd57af07?v\u003d1711007961\"\u003e\u003c/center\u003e\u003cp\u003e这个分布式存储系统包含一组后端服务器和一个主服务器。后端服务器彼此不同,但它们存储相同的数据,而且对客户端都是不可见的。当客户端机器需要一个文件时,它会向主服务器发送请求。主服务器从一些后端服务器收集文件的不同部分。主服务器的策略如下。\u003c/p\u003e\u003cp\u003e每个后端服务器都有自己的处理吞吐量和传输带宽。主服务器知道第i个后端服务器的吞吐量为p\u003csub\u003ei\u003c/sub\u003e(MB/s),带宽为b\u003csub\u003ei\u003c/sub\u003e(MB/s)。因此,忽略传播时间,处理大小为f\u003csub\u003ei\u003c/sub\u003e MB的数据并发送到主机需要的时间为:\u003c/p\u003e\u003ccenter\u003e\u003cp\u003e总时间 \u003d 处理时间 + 传输时间 \u003d f\u003csub\u003ei\u003c/sub\u003e / p\u003csub\u003ei\u003c/sub\u003e + f\u003csub\u003ei\u003c/sub\u003e / b\u003csub\u003ei\u003c/sub\u003e\u003c/p\u003e\u003c/center\u003e\u003cp\u003e此外,在第i台服务器上处理1 MB数据的成本为c\u003csub\u003ei\u003c/sub\u003e(包括电力消耗和维护成本等)。为了最小化总成本,主服务器应仔细决定应该使用哪些后端服务器以及它们应该处理多少负载。同时,由于一些一致性考虑,每次主服务器应该选择确切的\u003cb\u003eK\u003c/b\u003e个后端服务器来提取文件,并且每个后端服务器应该在相同的时间内完成工作。\u003c/p\u003e\u003cp\u003e你的任务是为主服务器编写一个调度程序。假设文件的大小为\u003cb\u003eF\u003c/b\u003e MB,文件可以被无限分割。\u003c/p\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003e第一行包含两个整数\u003cb\u003eN\u003c/b\u003e和\u003cb\u003eK\u003c/b\u003e(\u003cb\u003eK\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ 20000),以及一个实数\u003cb\u003eF\u003c/b\u003e。主服务器应该在总共\u003cb\u003eN\u003c/b\u003e台后端服务器中选择恰好K台。 \u003cb\u003eF\u003c/b\u003e是文件的大小。\u003c/p\u003e\u003cp\u003e接下来的\u003cb\u003eN\u003c/b\u003e行描述每台后端服务器的详细信息。每行包含三个实数,p\u003csub\u003ei\u003c/sub\u003e、b\u003csub\u003ei\u003c/sub\u003e和c\u003csub\u003ei\u003c/sub\u003e,表示处理吞吐量、带宽和单位成本。\u003c/p\u003e\u003c/div\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003e输出文件只包含一个实数,即最小成本。答案小于10000000000,应四舍五入到四位小数。\u003c/p\u003e\u003c/div\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2 2\r\n1 1 2\r\n1 1 1\r\n2 2 10\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3.0000\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"在示例情况下,主服务器应选择前两台后端服务器。它们每台应处理文件的1 MB部分(总共2 MB),以使完成时间相同(2秒)。总成本为1*2+1*1 \u003d 3.0000"}}]}