首页 > 代码库 > 【BZOJ4868】期末考试 [三分][贪心]
【BZOJ4868】期末考试 [三分][贪心]
期末考试
Time Limit: 20 Sec Memory Limit: 512 MB[Submit][Status][Discuss]
Description
Input
Output
Sample Input
100 100 2
4 5
5 1 2 3
1 1 2 3 3
4 5
5 1 2 3
1 1 2 3 3
Sample Output
6
HINT
Solution
首先，由于学生需要知道所有的成绩，这意味着即使只有一个成绩不知道，代价也是要算的，那么显然答案只和所有成绩都发出的时间有关。
显然，如果我们知道了所有成绩都发出的时间，必然是可以算出最小的不愉快度的，对于一个最后日期x，我们运用贪心得到不愉快度：
1.由于A策略有负面影响，B策略没有，所有在A<B的情况下才有可能用A
2.如果我们需要用A，显然能用的次数是：所有天数在x前面的 (x-天数)，剩下的用B补满。
然后，我们大胆猜测可以三分！这样我们就能AC啦。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 using namespace std; 9 typedef long long s64;10 11 const int ONE = 1000001;12 const s64 INF = 1e18;13 14 int A,B,C,n,m; 15 int t[ONE],b[ONE],MaxN;16 s64 Ans = INF;17 int Now;18 19 inline s64 get()20 {21 s64 res=1,Q=1; char c;22 while( (c=getchar())<48 || c>57)23 if(c==‘-‘)Q=-1;24 if(Q) res=c-48; 25 while((c=getchar())>=48 && c<=57) 26 res=res*10+c-48;27 return res*Q; 28 }29 30 s64 Judge(s64 x)31 {32 s64 res = 0, num1 = 0, num2 = 0;33 for(int i=1;i<=n;i++) res += max(x-t[i],0LL) * C;34 for(int i=1;i<=m;i++) num1 += max(x-b[i],0LL), num2 += max(b[i]-x,0LL);35 if(A > B) res += num2 * B;36 else37 {38 res += min(num1,num2) * A;39 res += max((num2-num1) * B,0LL);40 }41 42 Ans = min(Ans,res);43 return res;44 }45 46 int main()47 {48 A=get(); B=get(); C=get();49 n=get(); m=get();50 for(int i=1;i<=n;i++) t[i]=get(), MaxN=max(MaxN,t[i]);51 for(int i=1;i<=m;i++) b[i]=get();52 53 if(C >= 1e16)54 {55 for(int i=1;i<=n;i++) MaxN=min(MaxN,t[i]);56 printf("%lld",Judge(MaxN));57 }58 59 s64 a,b,pass;60 s64 l = 0, r = MaxN+1;61 while(l < r-2)62 {63 pass = (r-l)/3; 64 a = l+pass; b = r-pass;65 if(Judge(a) < Judge(b)) r = b;66 else l = a;67 }68 69 printf("%lld",Ans);70 71 } 72
【BZOJ4868】期末考试 [三分][贪心]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。