01分数规划
有\(n\)个物品，每个物品有两个权值\(a_{i}\),\(b_{i}\),现在要去掉\(k\)个 物品，使得剩下的\(n-k\)个物品 \(\frac{\sum a_{i}}{\sum b_{i}}\)
有最大值，并求出该最大值。
\(\frac{\sum a_{i}}{\sum b_{i}}\) = \(\frac{\sum a_{i} * w_{i}}{\sum b_{i} * w_{i}}\) (\(w_{i}\) = 0 / 1 表示物品是否选择) \(\ge\) \(X\)
\(\sum a_{i} * w_{i}\) - \(X\) * \(\sum b_{i} * w_{i}\) \(\ge\) \(0\)
\(\sum w_{i}\) * (\(a_{i}\) - \(X\) * \(b_{i}\)) \(\ge\) \(0\)
将 \(a_{i}\) - \(X\) * \(b_{i}\) 看作物品的新权值，按照权值大小排序，将 $n - k $个加和 看是否 \(\ge\) \(0\)
现在只需要找到 最大的\(X\) 使不等式成立 ，
二分答案 ！ 找到 \(X\) 的二分区间！
[放弃测试](234. 放弃测试 - AcWing题库)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2e3 + 50;
int n,k;
int a[N],b[N];
double c[N];
bool check(double x)
{
for(int i = 1; i <= n; i++)
c[i] = a[i] - x * b[i];
sort(c+1,c+n+1);
double ans = 0;
for(int i = k + 1; i <= n; i ++) ans += c[i];
if(ans < 0) return false;
else return true;
}
int main()
{
while(1) {
scanf("%d%d",&n,&k);
if(n == 0 && k == 0) break;
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
for(int i = 1; i <= n; i++) scanf("%d",&b[i]);
double l = 0, r = 1;
while(l + 1e-5 < r)
{
double mid = (l + r) / 2;
if(check(mid) == true) l = mid;
else r = mid;
}
printf("%.0lf\n",r * 100);
}
return 0;
}
[观光奶牛](361. 观光奶牛 - AcWing题库)
有向图环-> SPFA
\(\frac{\sum f_{i}}{\sum t_{i}}\) = \(\frac{\sum f_{i} * w_{i}}{\sum t_{i} * w_{i}}\) \(\ge\) \(X\)
\(\sum w_{i} * (f_{i} - X * t_{i}) \ge 0\)
\(\sum w_{i} * (X * t_{i} - f_{i}) \le 0\)
令 新边权 为 \(X * t_{i} - f_{i}\) 跑一遍 SPFA 看看 有没有 负环
由于不清楚有向图的起点和连通性，每个点都要 跑一遍，以防错漏负环
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 2e4 + 50;
const int INF = 1e8 + 91;
int n,m;
int f[N];
struct node{
int from;
int to;
int dis;
int next;
}e[N];
int cnt;
int head[N];
double mapp[N];
void add(int u,int v,int w)
{
cnt++;
e[cnt].from = u;
e[cnt].to = v;
e[cnt].dis = w;
e[cnt].next = head[u];
head[u] = cnt;
}
bool vis[N];
int num[N];
bool SPFA(double t)
{
queue<int> q;
for(int i = 1; i <= n; i++) {
vis[i] = true; mapp[i] = INF; num[i] = 0;
q.push(i);// 关键
}
while(!q.empty())
{
int x = q.front();
vis[x] = false;
q.pop();
for(int i = head[x]; i ; i = e[i].next)
{
int y = e[i].to;
double val = e[i].dis * t - f[x];// 新边权
if(mapp[x] + val < mapp[y])
{
mapp[y] = mapp[x] + val;// spfa 最短路 板子
num[y] = num[x] + 1;
if(num[y] >= n) return true;// 有 负环
if(vis[y] == false) q.push(y);
}
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) scanf("%d",&f[i]);
for(int i = 1; i <= m; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
double l = 0, r = 1e3 + 20;
while(l + 1e-5 < r)
{
double mid = (l + r) / 2;
if(SPFA(mid) == true) l = mid;
else r = mid;
}
printf("%.2f",r);
return 0;
}