二分還沒(méi)搞出來(lái)~~一直超時(shí)~~迭代感覺(jué)也是利用了單調(diào)性~~不斷地逼近
迭代代碼：
#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);//這個(gè)比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;
}
二分開(kāi)始一直超時(shí)~~~結(jié)果~~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
用堆做，但是發(fā)現(xiàn)當(dāng)極限數(shù)據(jù)的a[i]很大，達(dá)到10^9的時(shí)候，然后k又很小，這樣的數(shù)據(jù)是會(huì)跑死的
而用二分答案的方法開(kāi)始我有去想，但是，不知道該怎么去判斷，其實(shí)在用堆作處理的時(shí)候，我已經(jīng)用到了，先將每次自然干的1/m進(jìn)行平攤，然后判斷特殊的烘烤的次數(shù)。而后判斷烘烤次數(shù)是否能超過(guò)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 閱讀(304)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
acm