题意:
思路:
纯看题解的题QAQ
首先可以把题目中的式子化成这样
所以可以把每个(ti-T)分成两类,一类正,一类负。
用贪心的思想,可以发现有一半必须全选,另一半选最靠近T的那些,因为ti-T越小,xi越大。
所以排序之后贪心就可以了。
涨姿势了原来这题目是这么做的。
可是这道题我debug了很久QAQ到现在我也不知道之前WA的写法错哪儿了 我只不过把之前负的的计数改成了正的 就AC了 很奇怪 不知道错哪儿了 很迷QAQ
代码:
typedef long long ll;
struct node
{
ll a,t;
} nd[200010];
bool cmp1(node x,node y)
{
return x.t<y.t;
}
bool cmp2(node x,node y)
{
return x.t>y.t;
}
int main()
{
int n;
ll T;
scanf("%d%lld",&n,&T);
for(int i=0; i<n; i++)
scanf("%lld",&nd[i].a);
for(int i=0; i<n; i++)
{
scanf("%lld",&nd[i].t);
nd[i].t-=T;
}
double ansn=0,ansp=0;
ll stn=0,stp=0;
for(int i=0; i<n; i++)
{
if(nd[i].t<0){stn-=nd[i].a*nd[i].t;ansn+=1.0*nd[i].a;}
else {stp+=nd[i].a*nd[i].t;ansp+=1.0*nd[i].a;}
}
//printf("%lld %lld\n",stn,stp);
if(stn<stp)
{
sort(nd,nd+n,cmp1);//把负的当少的
for(int i=0; i<n; i++)
{
if(nd[i].t>=0)
{
if(stn-1.0*nd[i].a*nd[i].t>=0)
{
stn-=nd[i].a*nd[i].t;
ansn+=1.0*nd[i].a;
}
else
{
ansn+=stn/(1.0*nd[i].t);
stn=0;
break;
}
}
}
printf("%.15f\n",ansn);
}
else
{
sort(nd,nd+n,cmp2);//把正的当少的
for(int i=0; i<n; i++)
{
if(nd[i].t<0)
{
if(stp-1.0*nd[i].a*(-nd[i].t)>=0)
{
stp-=nd[i].a*(-nd[i].t);
ansp+=1.0*nd[i].a;
}
else
{
ansp+=stp/(-1.0*nd[i].t);
stp=0;
break;
}
}
}
printf("%.15f\n",ansp);
}
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!