描述
Demy有n颗宝石。她的每个珠宝都有一些价值vi和重量wi。自从丈夫约翰在最近的金融危机爆发后，已经决定出售一些珠宝。她决定自己会保留最好的珠宝。她决定保留这样的宝石，使他们的具体价值尽可能大。也就是说，表示某组宝石S = {i1，i2，...，ik}的具体值。
Demy想选择这样的k宝石，他们的具体值是最大可能的。帮助她这样做。
输入
输入文件的第一行包含n - Demy得到的珠宝数量，k - 她想保留的珠宝数量（1≤k≤n≤100 000）。
以下n行包含两个整数，每个-vi和wi（0≤vi≤10e6,1≤wi≤10e6，所有vi的和和全部wi之和不超过10e7）。
输出
输出k个数字 - 戴姆必须保留的珠宝数量。如果有几个解决方案，输出任何一个。
样例输入
3 2
1 1
1 2
1 3
样例输出
1 2
题目大意：
n个珠宝，每个珠宝对应一个重量wi和价值vi，现在要从中找出k个，使的这k个珠宝的单位重量的价值最大，输出这k个珠宝的编号。
解题思路：
首先，我们给出一个贪心思路：计算出每个珠宝的单位价值，从大到小选择k个，这个贪心思路是显然错误的。感性证明：单位价值只体现了比值，在数值大小不一样的时候，比值不可做加法。
所以，我们来换一个角度：
我们设一个集合S的单位价值≥x
则有
∑vi / ∑wi ≥ x （i∈S）
变形得
∑（vi - x × wi ）≥0（i∈S）
所以，对vi-x×wi排序，选择前k个，检验是否≥0
而x我们可以通过二分来枚举
Code
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register int
#define ll long long
#define inf (1<<30)
#define eps (1e-15)
#define maxn 100005
#define rep(i,a,b) for(RG i=a;i<=b;i++)
#define per(i,a,b) for(RG i=a;i>=b;i--)
using namespace std;
int n,k;
struct Dat{
double v,w;
}dat[maxn];
double tmp[maxn];
inline int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} inline bool cmp(const double &a,const double &b)
{
return a>b;
} inline bool judge(double x)
{
rep(i,,n) tmp[i]=dat[i].v-x*dat[i].w;
sort(tmp+,tmp++n,cmp);
double sum=;
rep(i,,k) sum+=tmp[i];
return sum>=;
} struct Ans{
int id;
double val;
}ans[maxn]; inline bool cmp2(const Ans &a,const Ans &b)
{
return a.val>b.val;
} inline void work(double x)
{
rep(i,,n) ans[i].id=i,ans[i].val=dat[i].v-x*dat[i].w;
sort(ans+,ans++n,cmp2);
rep(i,,k) printf("%d ",ans[i].id);
} void solve()
{
double l=,r=inf;
rep(i,,)
{
double mid=(l+r)/;
if(judge(mid)) l=mid;
else r=mid;
}
work(r);
} int main()
{
n=read(),k=read();
rep(i,,n) dat[i].v=read(),dat[i].w=read();
solve();
return ;
}
点击展开代码