【Luogu】P3745期末考试（三分）

　　题目链接

　　我是怎么把“期末考试”在本地写成“假期计划”的

　　qwq？？？？

　　本题把学生和卷子都排个序，按出成绩最晚时间三分。

　　三分之后可以O（n）的时间统计答案，因为修改卷子出成绩的时间可以贪心计划。

　　这里着重了解一下为什么可以三分。

　　我们可以发现随着出成绩的时间推迟，学生的不偷税愉悦度肯定是越来越大的，换句话说这玩意单调递增。

　　然而老师的不偷税度一定是越来越小的，换句话说这玩意单调递减。

　　所以说这俩玩意加起来肯定跟二次函数长得特像。

　　就可以三分啦。

　　然而三分是用于实数定义域内的，我们这是整数怎么办？

　　所以说我们可以三分取得一个较小的区间（我这里定的区间大小=8）

　　然后对这个区间每一个值都求一遍求解就好啦

#include<cstdio>

#include<cstdlib>

#include<cctype>

#include<cstring>

#include<algorithm>

#define maxn 200020

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

long long a,b,c;

long long n,m;

long long q[maxn];

long long d[maxn];

double calc(long long x){

    long long rest=,need=;

    for(long long i=;i<=m;++i)

        if(q[i]<=x)    rest+=x-q[i];

        else         need+=q[i]-x;

    double ans=;

    if(a<b){

        if(need<=rest)    ans=a*need;

        else ans=a*rest+b*(need-rest);

    }

    else ans=b*need;

    for(long long i=;i<=n;++i)

        if(d[i]<x){

            //if(c==1e16)    return 1e18;

            ans+=(double)(x-d[i])*c;

        }

    return ans;

}

int main(){

    a=read(),b=read(),c=read();

    n=read(),m=read();

    for(long long i=;i<=n;++i)    d[i]=read();

    for(long long i=;i<=m;++i)    q[i]=read();

    sort(d+,d+n+);

    sort(q+,q+m+);

    long long l=d[],r=d[n];

    while(r-l>){

        long long mid=l+(r-l)/;

        long long mmid=l+(r-l)*/;

        if(calc(mid)<=calc(mmid))    r=mmid;

        else l=mid;

    }

    long long ret=l;

    for(long long i=l;i<=r;++i)

        if(calc(i)<calc(ret))    ret=i;

    printf("%.0lf",calc(ret));

    return ;

}

巴特西

【Luogu】P3745期末考试（三分）

最新文章

热门文章