网站建设响应式是什么,两个网站合并建设实施方案,建设银行徐州分行网站,福州仿站定制模板建站题意#xff1a;
给你若n个分数#xff0c;分子a[i]a[i]a[i],分母b[i]b[i]b[i],使满足公式100⋅∑i1nai∑i1nbi100\cdot\tfrac{\sum_{i1}^{n} a_{i}}{\sum_{i1}^{n} b_{i}}100⋅∑i1nbi∑i1nai#xff0c;求任意去掉k个分数后#xff0c;公式结果最大值。
题目…题意
给你若n个分数分子a[i]a[i]a[i],分母b[i]b[i]b[i],使满足公式100⋅∑i1nai∑i1nbi100\cdot\tfrac{\sum_{i1}^{n} a_{i}}{\sum_{i1}^{n} b_{i}}100⋅∑i1nbi∑i1nai求任意去掉k个分数后公式结果最大值。
题目
In a certain course, you take n tests. If you get aia_{i}ai out of bib_{i}bi questions correct on test i, your cumulative average is defined to be
100⋅∑i1nai∑i1nbi100\cdot\tfrac{\sum_{i1}^{n} a_{i}}{\sum_{i1}^{n} b_{i}}100⋅∑i1nbi∑i1nai
Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.
Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is 100⋅502516100\cdot\tfrac{502}{516}100⋅516502. However, if you drop the third test, your cumulative average becomes 100⋅5051≈83.33≈83100\cdot\tfrac{50}{51}\approx83.33\approx83100⋅5150≈83.33≈83.
Input
The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤ k n. The second line contains n integers indicating ai for all i. The third line contains n positive integers indicating bi for all i. It is guaranteed that 0 ≤ ai ≤ bi ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n k 0 and should not be processed.
Output
For each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.
Sample Input
3 1 5 0 2 5 1 6 4 2 1 2 7 9 5 6 7 9 0 0
Sample Output
83 100
Hint
To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).
分析
01分数规划 简单的来说就是有一些二元组aibi从中选取一些二元组使得∑ai / ∑bi最大最小。 这种题一类通用的解法就是我们假设x ∑ai / ∑bi的最大小值那么就有x * ∑ai ∑bi ,即∑ai - x * ∑bi 0。也就是说当某一个值x满足上述式子的时候它就是要求的值。我们可以想到枚举……不过再想想这个可以二分答案。 所以我们直接二分答案当上述式子0,说明答案小了0则说明答案大了这样计算即可。 01分数规划问题相关算法详解
AC代码
#includestdio.h
#includestring.h
#includeiostream
#includealgorithm
using namespace std;
const int M1e310;
const double eps1e-4;
int n,m;
double a[M],b[M],c[M];
bool cmp(double u,double v){return uv;
}
bool dfs(double x){for(int i0;in;i){c[i]a[i]-x*b[i];}sort(c,cn,cmp);double ans0.0;for(int i0;in-m;i)ansc[i];if(ans0) return true;return false;
}
int main(){while(~scanf(%d%d,n,m)){if(n0m0)break;for(int i0;in;i)scanf(%lf,a[i]);for(int i0;in;i)scanf(%lf,b[i]);double r0.0,l1.0;while(l-reps){double mid(rl)/2;if(dfs(mid)) rmid;else lmid;}printf(%.0f\n,r*100);}return 0;
}
基本01分数规划问题
给定 n 个二元组 (ai,bia_{i},b_{i}ai,bi ) aia_{i}ai是选择此二元组获得的价值非负bib_{i}bi是选择此二元组付出的代价非负设 xix_{i}xi (xix_{i}xi ∈ { 0 , 1 } ) 代表第 i个二元组的选与不选最大(小)化下式 max(ormax(ormax(or min)min)min) r∑i1nai⋅xi∑i1nbi⋅xir\tfrac{\sum_{i1}^{n} a_{i}\cdot x_{i}}{\sum_{i1}^{n} b_{i}\cdot x_{i}}r∑i1nbi⋅xi∑i1nai⋅xi 下面先说最大化
解决方法:二分法
设 r最大值为r∗r^{∗}r∗ r∗r^{∗}r∗∑i1nai⋅xi∑i1nbi⋅xi\tfrac{\sum_{i1}^{n} a_{i}\cdot x_{i}}{\sum_{i1}^{n} b_{i}\cdot x_{i}}∑i1nbi⋅xi∑i1nai⋅xi ⇔\Leftrightarrow⇔ ∑ai⋅xi−r∗⋅∑bi⋅xi0\sum a_{i}\cdot x_{i}-r^{*}\cdot\sum b_{i}\cdot x_{i}0∑ai⋅xi−r∗⋅∑bi⋅xi0 设一个函数自变量为 r值 f(r)f ( r )f(r) ∑ai⋅xi−r∗⋅∑bi⋅xi\sum a_{i}\cdot x_{i}-r^{*}\cdot\sum b_{i}\cdot x_{i}∑ai⋅xi−r∗⋅∑bi⋅xi
观察这个函数假如xi{x_{i}}xi固定则这个函数就是坐标系中一条直线( y B − A ⋅ x)每一组xix_{i}xi对应着一条直线这些直线斜率非正(因为 − A − ∑bi⋅xib_{i} ⋅ x_{i}bi⋅xi ≤ 0)纵截距非负(因为 B ∑ai⋅xi≥0)a_{i}⋅ x_{i} ≥ 0)ai⋅xi≥0),如图1。
对于每一条直线当f(r)0f ( r ) 0f(r)0时横截距就是这一组的 r那么r∗r^{*}r∗ 就是每条直线横截距的最大值每组xix_{i}xi对应r的最大值如图2。
在图中上任取一条垂直x轴的竖线 如果存在直线与这条竖线的交点纵坐标为正那么最优值一定在当前竖线的右侧 如果所有直线与这条竖线交点纵坐标为负那么最优值一定在当前竖线的左侧 如果所有直线与这条竖线交点纵坐标非正且存在直线与这条竖线交点纵坐标为0那么当前竖线横坐标即为最优值r∗r^{*}r∗ 。
按照这个思想可以二分答案r那么二分时如何进行判断呢
选择一个 r时需要判断所有 f(r)f ( r )f(r)的最大值是否为0如果 maxm a xmax {f(r)f ( r )f(r) } 0则 r r∗r^{∗}r∗ 怎样求 maxf(r)m a x { f ( r ) }maxf(r)? f(r)f ( r )f(r) ∑ai⋅xi−r⋅∑bi⋅xi\sum a_{i}\cdot x_{i}-r\cdot\sum b_{i}\cdot x_{i}∑ai⋅xi−r⋅∑bi⋅xi ⇔\Leftrightarrow⇔∑ai−r⋅bi)⋅xi\sum a_{i}-r\cdot b_{i})\cdot x_{i}∑ai−r⋅bi)⋅xi 二分一个 r时每个二元组的ai−r⋅bi)⋅xi a_{i}-r\cdot b_{i})\cdot x_{i}ai−r⋅bi)⋅xi都可以求出设其为weightiweight_{i}weighti现在的目标就是找到一组 xix_{i}xi使得 ∑ wighti⋅xiw i g h t _{i} ⋅ x_{ i}wighti⋅xi 最大即求maxf(r)m a x { f ( r ) }maxf(r))。怎么找到这一组xix_{i}xi或者直接求得 maxf(r)m a x { f ( r ) }maxf(r) 呢具体问题具体分析经常借助最短路算法判断是否存在负环。
