题解：P12519 「MSTOI-R1」热开水

Vocaloid世末歌者 · 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;
}