自动搬运

查看原文

来自洛谷，原作者为

	Vocaloid世末歌者 私の歌声今も絶えない|想要互关犇犇@我|粉丝群249052020|已设置“仅关注的人和管理员”私信权限。有事犇犇@我

搬运于2025-08-24 23:16:09，当前版本为作者最后更新于2025-05-17 21:52:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言：mst 可爱喵/qq

验题人写个题解。

发现有单调性且是经典的“最早在第几天”，于是考虑二分。

check 函数按计算方式暴力找出现在的 $rks$ 即可，详见代码。

有个比较奶龙的地方是（不知道你们会不会踩这个坑），要小心精度的问题，要开 double，而且计算时要 (double) 而不是 1.0*。

#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void writing(i128 x)
{
	if(x>=10)writing(x/10);
	putchar(x%10+'0');
}
void write(i128 x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	writing(x);
}
LL n;
double m;
struct song
{
	double a,b,c;
}a[100010];
double bl(double x)
{
	LL y;
	double z;
	x*=100;
	y=x;
	z=y/100.0;
	return z;
}
struct son
{
	double rks,acc;
}b[100010];
double d[10],td[10],sum,mc,tt[20];
LL l=-1,r=1000000001,mid;
bool cmp(son x,son y)
{
	return x.rks>y.rks;
}
bool che(LL mid)
{
//	cout<<mid<<"::"<<endl;
	if(mid==0)
	{
		sum=0;
		rep(i,1,5,1)
		{
			sum+=d[i];
			sum=bl(sum);
		}
		sum/=5;
		sum=bl(sum);
		return (sum>=m);
	}
	rep(i,1,5,1)td[i]=d[i];
	mc=0;
	rep(i,1,n,1)
	{
		b[i].acc=min((double)100,bl(a[i].a+bl((double)(mid-1)*a[i].b)));
		b[i].acc=bl(b[i].acc);
		if(b[i].acc>=(double)70)
		{
			b[i].rks=bl(bl(bl((b[i].acc-(double)55)/(double)45)*bl((b[i].acc-(double)55)/(double)45))*a[i].c);
		}
		else b[i].rks=0;
		if(b[i].acc==(double)100)
		{
			mc=max(mc,b[i].rks);
			mc=bl(mc);
		}
//		cout<<i<<':'<<b[i].rks<<' ';
	}
//	cout<<endl;
	sort(b+1,b+n+1,cmp);
	sum=0;
	rep(i,1,4,1)
	{
		tt[i]=td[i];
	}
	rep(i,5,8,1)
	{
		tt[i]=b[i-4].rks;
	}
	sort(tt+1,tt+8+1);
	rem(i,4,1,1)
	{
		td[i]=tt[8-i+1];
	}
	td[5]=max(td[5],mc);
	td[5]=bl(td[5]);
	rep(i,1,5,1)
	{
		sum+=td[i];
		sum=bl(sum);
	}
	sum/=5;
	sum=bl(sum);
//	cout<<mid<<' '<<sum<<endl;
	return (sum>=m);
}
int main()
{
	cin>>n>>m;
	rep(i,1,n,1)
	{
		cin>>a[i].a>>a[i].b>>a[i].c;
	}
	rep(i,1,5,1)cin>>d[i];
	while(l+1<r)
	{
		mid=l+r>>1;
		if(che(mid))r=mid;
		else l=mid;
	}
	if(!che(r))cout<<-1<<endl;
	else cout<<r<<endl;
	return 0;
}