手机网站建设语言,设计说明怎么写模板,青岛网站排名方案,eclipse可以做门户网站嘛[P9559 SDCPC2023] Fast and Fat - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路#xff1a;最小值最大#xff0c;二分答案。
发现对于 w i ≥ w j w_i \ge w_j wi≥wj时#xff0c;第 i i i个人速度不变#xff0c;还是 v i v_i vi#xff0c;但是第 j j j…[P9559 SDCPC2023] Fast and Fat - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路最小值最大二分答案。
发现对于 w i ≥ w j w_i \ge w_j wi≥wj时第 i i i个人速度不变还是 v i v_i vi但是第 j j j个人速度会变为 v j − ( w i − w j ) v_j - (w_i - w_j) vj−(wi−wj)。直接二分答案的话假设此时为 m i d mid mid那么速度小于 m i d mid mid的人需要人来带且速度要至少提到 m i d mid mid才符合要求。
且对于初始速度已经大于 m i d mid mid的来说可能要带速度小于 m i d mid mid的人而且大于 m i d mid mid的人要带的人的体重差也要满足一定条件即要符合 v j − ( w i − w j ) ≥ m i d v_j - (w_i - w_j) \ge mid vj−(wi−wj)≥mid最差情况是 v j − ( w i − w j ) m i d v_j - (w_i - w_j) mid vj−(wi−wj)mid进而得到所承受的最大重量为 w i v j w j − m i d w_i v_j w_j - mid wivjwj−mid。此时发现在最大重量中 v j w j v_j w_j vjwj是不变的 v j w j − m i d v_j w_j - mid vjwj−mid是单调的。
对于需要两两组合的情况显示是可能出现经过特定构造可以满足但是随机分配是不满足的情况此时还要贪心的进行配对。我们可以复制一份每个人的信息 v , w v,w v,w。对于其中一个按照 v i w i v_i w_i viwi进行排序对于另一个按照 w i w_i wi进行排序这样就贪心的保证速度大于 m i d mid mid的人可以分配的最大体重的值跟速度小于 m i d mid mid的人的最大体重值相配对次大依次类推避免出现浪费 v i w i v_i w_i viwi和 w j w_j wj的情况且如果这样都不行那么一定不存在可行方案。
代码如下
void solve() {int n; cinn;vectorarrayint,2 a(n); // v wfor(auto t: a) cint[0]t[1];auto b(a);// 按 v w 进行排序sort(a.begin(), a.end(), [](auto pre, auto suf) {return pre[0] pre[1] suf[0] suf[1];});// 按 w 进行排序sort(b.begin(), b.end(), [](auto pre, auto suf) {return pre[1] suf[1];});// pre为速度大于mid的suf是速度小于mid// 得到pre可以带的最大体重suf的体重进行配对auto check [](int mid) - bool {vectorint pre, suf;for(int i 0; i n; i) {if(a[i][0] mid) pre.push_back(a[i][0] a[i][1] - mid);if(b[i][0] mid) suf.push_back(b[i][1]);}// 如果小于mid的人的数量大于速度大于mid的那么一定不可以if(suf.size() pre.size()) return false;int m suf.size();for(int i 0; i m; i) {// 如果速度大于mid的人能带的最大体重小于速度小于mid的体重那么就不行if(suf[i] pre[i]) return false;}return true;};// 最小值最大int l 0, r 1e9;while(l r) {int mid l r 1 1;if(check(mid)) l mid;else r mid - 1;}coutl\n;
}
