二分还没搞出来~~一直超时~~迭代感觉也是利用了单调性~~不断地逼近
迭代代码：
#include<iostream>
#include<algorithm>
#include<math.h>
#define inf 1.0e-8
#define maxn 100005
using namespace std;
struct node
{
int w,v,i;
double c;
friend bool operator<(const node &a,const node& b)//加了const &快了很多
{
return a.c>b.c;
}
}in[maxn];
int n,k;
int main()
{
scanf("%d%d",&n,&k);
int i;
double up,down;
for(up=down=i=0;i<n;i++)
{
scanf("%d%d",&in[i].v,&in[i].w);
in[i].i=i+1;
}
for(i=0;i<k;i++)
{
up+=in[i].v;
down+=in[i].w;
}
double s=(up+0.0)/down,last=0.0;
while(fabs(s-last)>=inf)
{
for(i=0;i<n;i++)
in[i].c=in[i].v-s*in[i].w;
nth_element(in,in+k,in+n);//这个比partial_sort()快很多，毕竟后面的前k都排序了
for(up=down=0.0,i=0;i<k;i++)
{
up+=in[i].v;
down+=in[i].w;
}
last=s;
s=(up+0.0)/down;
}
for(i=0;i<k;i++)
{
printf("%d",in[i].i);
i==k-1?printf("\n"):printf(" ");
}
return 0;
}
二分开始一直超时~~~结果~~const &真的不能忽视~~差距太大了
二分代码：
#include<iostream>
#include<algorithm>
#include<math.h>
#define maxn 100005
#define inf 1e-6
using namespace std;
int n,k;
struct node
{
int v,w,i;
double change;
friend bool operator<(const node& a,const node& b)
{
return a.change>b.change;
}
}in[maxn];
int ansk[maxn];
int main()
{
scanf("%d%d",&n,&k);
int i;
for(i=0;i<n;i++)
{
scanf("%d%d",&in[i].v,&in[i].w);
in[i].i=i;
}
double low=0,high=1000000;
while(fabs(low-high)>inf)
{
double mid=(low+high)/2.0,sum=0.0;
for(i=0;i<n;i++)
in[i].change=in[i].v-mid*in[i].w;
nth_element(in,in+k,in+n);
for(i=0;i<k;i++)
sum+=in[i].change;
if(sum<0.0)high=mid;
else
{
for(i=0;i<k;i++)
ansk[i]=in[i].i;
low=mid;
}
}
for(i=0;i<k;i++)
{
printf("%d",ansk[i]+1);
i==k-1?printf("\n"):printf(" ");
}
return 0;
}
pku 3104
用堆做，但是发现当极限数据的a[i]很大，达到10^9的时候，然后k又很小，这样的数据是会跑死的
而用二分答案的方法开始我有去想，但是，不知道该怎么去判断，其实在用堆作处理的时候，我已经用到了，先将每次自然干的1/m进行平摊，然后判断特殊的烘烤的次数。而后判断烘烤次数是否能超过mid要求
以下是代码：
#include<iostream>
#define maxn 100005
#define max(a,b) (a>b?a:b)
int n,k,a[maxn];
int main()
{
int i;
// freopen("1","r",stdin);
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&k);
int low=0,high=1000000000;
if(k==1)
{
for(i=0;i<n;i++)
low=max(low,a[i]);
} while(low<=high&&k!=1)
{
int mid=(low+high)/2;
int nt=0;
for(i=0;i<n;i++)
{
if(a[i]<=mid)continue;
if((a[i]-mid)%(k-1))
nt+=(a[i]-mid)/(k-1)+1;
else nt+=(a[i]-mid)/(k-1);
if(nt>mid)break;
}
if(i==n)high=mid-1;
else low=mid+1;
}
printf("%d\n",low);
return 0;
}
posted on 2008-10-11 03:30
zoyi 阅读(272)
评论(0) 编辑 收藏 引用 所属分类:
acm