首页 > 代码库 > [POJ3111]K Best
[POJ3111]K Best
来源：
Northeastern Europe 2005, Northern Subregion
思路：
分数规划经典题。二分分数值$x$，判断其是否满足$\sum (v - w \times m) \geq 0$即可。
针对$v - w \times m$从大到小排序，然后对前$k$项求和，检验是否非负。
1 #include<cstdio> 2 #include<cctype> 3 #include<vector> 4 #include<algorithm> 5 #include<functional> 6 inline int getint() { 7 char ch; 8 while(!isdigit(ch=getchar())); 9 int x=ch^‘0‘;10 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^‘0‘);11 return x;12 }13 const double eps=1e-6;14 const int N=100000;15 int n,k;16 struct Jewel {17 int v,w,id;18 double sum;19 bool operator > (const Jewel &x) const {20 return sum>x.sum;21 }22 };23 Jewel j[N];24 std::vector<int> ans;25 inline bool check(const double x) {26 ans.clear();27 for(int i=0;i<n;i++) {28 j[i].sum=j[i].v-j[i].w*x;29 }30 std::sort(&j[0],&j[n],std::greater<Jewel>());31 double sum=0;32 for(int i=0;i<k;i++) {33 sum+=j[i].sum;34 ans.push_back(j[i].id);35 }36 return sum>=0;37 }38 int main() {39 n=getint(),k=getint();40 for(int i=0;i<n;i++) {41 j[i].v=getint();42 j[i].w=getint();43 j[i].id=i+1;44 }45 double l=0,r=1000000;46 while(r-l>=eps) {47 double mid=(l+r)/2;48 if(check(mid)) {49 l=mid;50 }51 else {52 r=mid;53 }54 }55 for(unsigned i=0;i<ans.size();i++) {56 printf("%d ",ans[i]);57 }58 return 0;59 }
[POJ3111]K Best
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。