HBC223548[NOIP2000]税收与补贴问题,数学,枚举,NOIP复赛JoiningFlows题解

一个忧伤的美男子算法基础篇 2023-11-11 23:38:02 47 0

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

The heart of the factory is the Chocolate River, where raw molten chocolate flows from k chocolate-producing faucets, to outlets where different types of pralines and choclate bars are made. The i’th of the k chocolate faucets produces chocolate at some fixed temperature. , and the amount of chocolate flowing from the faucet can be adjusted to any value between ai and bi millilitres per second. Suppose the k taps are adjusted to produce. frac{x_1t_1 + x_2t_2 + . . . + x_kt_k}{x_1 + x_2 + . . . + x_k }. Each type of praline and chocolate bar produced at the factory requires the Chocolate River to be adjusted to have a specific temperature and flow level. Charlie recently came across a long list of new praline recipies, and would now like to figure out which of these are even possible to make at the factory. Write a program to determine, for each of the new recipies, if its required temperature and flow level is possible to achieve with some setting of the k faucets.

Having recently taken over the Wonka Factory, Charlie is now in charge of the day-to-day production of the various chocolate products made there. While this may seem like a cushy job with an all-you-can-eat-chocolate perk, it also comes with the difficult responsibility of keeping the (somewhat convoluted and complicated) production lines working. The heart of the factory is the Chocolate River, where raw molten chocolate flows from k chocolate-producing faucets, to outlets where different types of pralines and choclate bars are made. The i’th of the k chocolate faucets produces chocolate at some fixed temperature t_i t i , and the amount of chocolate flowing from the faucet can be adjusted to any value between ai and bi millilitres per second. Suppose the k taps are adjusted to produce x_1,x_2,...,x_k x 1 ,x 2 ,...,x k millilitres of chocolates per second respectively (where a_ileq x_ileq b_i a i ≤x i ≤b i ). Then the total flow in the Chocolate river is x_1+x_2+...+x_k x 1 +x 2 +...+x k , and its temperature is the weighted average frac{x_1t_1 + x_2t_2 + . . . + x_kt_k}{x_1 + x_2 + . . . + x_k } x 1 +x 2 +...+x k x 1 t 1 +x 2 t 2 +...+x k t k (each faucet produces grade A quality chocolate which instantly mixes with the chocolate from the other faucets). Each type of praline and chocolate bar produced at the factory requires the Chocolate River to be adjusted to have a specific temperature and flow level. Charlie recently came across a long list of new praline recipies, and would now like to figure out which of these are even possible to make at the factory. Write a program to determine, for each of the new recipies, if its required temperature and flow level is possible to achieve with some setting of the k faucets.