JoiningFlows

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$ , 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$ millilitres of chocolates per second respectively (where $a_i\leq x_i\leq b_i$ ). Then the total flow in the Chocolate river is $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 }$

(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.

The first line of input contains an integer k (1 ≤ k ≤ 10), the number of taps. Then followk lines, describing the taps. The i’th of these lines contains the three integers ti, ai, and bi(0 ≤ ti ≤ $10^{6}$ , 0 ≤ ai ≤ bi ≤ $10^{6}$ ) describing the i’th faucet.

Next follows a line containing an integer r (1 ≤ r ≤ $10^{5}$ ), the number of new recipies tocheck. Then follows r lines, each describing a recipe. A recipe is described by two integersτ and φ (0 ≤ τ ≤ $10^{6}$ and 1 ≤ φ ≤ $10^{6}$ ), where τ is the chocolate temperature and φ thechocolate flow needed for this recipe.

#include<bits/stdc++.h> using namespace std; #define int long long const int N=30; #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int k, r; int maxf, minf, g; struct Node { int t, a, b; }node[N]; bool cmp(Node a, Node b) { return a.t<b.t; } signed main() { IOS cin>>k; for(int i=1;i<=k;i++) { cin>>node[i].t>>node[i].a>>node[i].b; maxf+=node[i].b; minf+=node[i].a; g+=node[i].a*node[i].t; } int r, f, sumn; double t; cin>>r; sort(node+1, node+k+1, cmp); for(int i=1;i<=r;i++) { int mi=0, ma=0; cin>>t>>f; if(f<minf||f>maxf) { cout<<"no"<<endl; continue; } sumn=f-minf; for(int j=1;j<=k;j++) { int x=(node[j].b-node[j].a); if(x<=sumn){ sumn-=x; mi+=node[j].t*x; } else{ mi+=sumn*node[j].t; break; } } sumn=f-minf; for(int j=k;j>=1;j--) { int x=(node[j].b-node[j].a); if(x<=sumn){ sumn-=x; ma+=node[j].t*x; } else{ ma+=sumn*node[j].t; break; } } double maa=(ma+g)*1.0/f, mii=(mi+g)*1.0/f; if(t<=maa&&t>=mii){ cout<<"yes"<<endl; } else cout<<"no"<<endl; } return 0; }

详情