并不对劲的bzoj4868: [Shoi2017]期末考试

传送门->

三分裸题。

发现答案只和最后一个科目公布成绩的时间有关。

科目公布成绩的时间越早，老师们的不愉快度越高，这个时间越晚，学生们的不愉快度越高。

它看上去像个单峰的，那么就三分好了。

判断时就是个简单的贪心。对于结束时间T，A>B时，让所有T后结束的科目的老师花B的不愉快度加速；B>A时，让所有T后结束的科目花A的不愉快度接受T前结束的科目老师，剩下的再花B的不愉快度加速。再统计学生的不愉快度，就能求出总不愉快度了。

据说三分、二分的题，看出它是道三分或二分的题就已经完成了一半。

 #include<algorithm>

 #include<cmath>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iomanip>

 #include<iostream>

 #include<map>

 #include<vector>

 #include<queue>

 #include<stack>

 #define rep(i,x,y) for(register ULL i=(x);i<=(y);++i)

 #define dwn(i,x,y) for(register ULL i=(x);i>=(y);--i)

 #define maxn 100010

 #define ULL unsigned long long

 using namespace std;

 ULL read()

 {

     ULL x=,f=;char ch=getchar();

     while(!isdigit(ch)&&ch!='-')ch=getchar();

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

     while(isdigit(ch))x=x*+ch-'',ch=getchar();

     return x*f;

 }

 void write(ULL x)

 {

     char ch[];ULL f=;

     if(!x){puts("");return;}

     if(x<){putchar('-');x=-x;}

     while(x)ch[++f]=x%+'',x/=;

     while(f)putchar(ch[f--]);

     putchar('\n');

 }

 ULL t[maxn],b[maxn],A,B,C,n,m,minc=-;

 ULL three=,two=,one=;

 void upd(ULL x){minc=minc==-?x:min(x,minc);}

 ULL getans(ULL T)

 {

 //    cout<<"T:"<<T<<" ";

     ULL ans=,tmp1=,tmp2=;

     rep(i,,m)

     {

         if(b[i]<=T)tmp1+=T-b[i];

         else tmp2+=b[i]-T;

     }

     if(tmp1<tmp2)ans=tmp1*A+(tmp2-tmp1)*B;

     else ans=tmp2*A;

     ans=min(ans,tmp2*B);

     rep(i,,n)if(t[i]<T)ans+=(T-t[i])*C;

     return ans;

 }

 int main()

 {

     A=read(),B=read(),C=read();

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

     rep(i,,n)t[i]=read();

     rep(i,,m)b[i]=read();

     sort(t+,t+n+),sort(b+,b+m+);

     ULL L=,R=b[m];

     while(R-L>=)

     {

         ULL lm=(R-L+one)/three+L,rm=(R-L+one)*two/three+L;

         //cout<<L<<" "<<lm<<" "<<rm<<" "<<R<<endl;

         ULL lans=getans(lm),rans=getans(rm);

         upd(lans),upd(rans);

         if(lans>rans) L=lm;

         else R=rm;

     }

     rep(i,L,R)upd(getans(i));

     write(minc);

     return ;

 }

 /*

 100 100 2

 4 5

 5 1 2 3

 1 1 2 3 3

 */

 /*

 3 5 4

 5 6

 1 1 4 7 8

 2 3 3 1 8 2

 */

以下与本题无关，勿看。

顺便说一些很令人不快的事情。

总有些人盲目地膜别人或者装弱，这听上去毫无意义。这样别人并不会觉得那个人有多谦虚，反而会很反感。这能够给乱膜者带来的弊大于利，他们也很清楚这一点，却还是要膜。这是为什么？我自以为，有的人可能是看着周围人都这么做，不想显得不合群，就也跟风模仿。也有人看着别人总膜自己，觉得不好意思，就也用同样的方式对付别人，这样就不会太别扭。这些只是被动的、不得不膜的人。但还有一些主动膜的人，才是带动盲目膜的不良风气的主力军。他们多半实力不低，却偏要以阴阳怪气的语气和奇怪的动作来贬低自己、抬高别人。这些可能只是被他们当成吸引别人注意的一种新奇手段。他们的另一个目的也不是在于表示谦虚，而是在于别人被膜之后说的“您那么强，怎么会弱呢”、“我比您菜多了”之类的话给他们带来的成就感。这一点上，就相当于是借对方之口嘲讽对方，给对方带来的困扰远多于直接批评讽刺。拒绝乱膜，从我做起！

巴特西

并不对劲的bzoj4868: [Shoi2017]期末考试

最新文章

热门文章