首页 > 代码库 > 【bzoj4868】[Shoi2017]期末考试 前缀和
【bzoj4868】[Shoi2017]期末考试 前缀和
题目描述
有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知所.有.课程的成绩。如果在第ti天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课程公布成绩，每等待一天就会产生C不愉快度。对于第i门课程，按照原本的计划，会在第bi天公布成绩。有如下两种操作可以调整公布成绩的时间：1.将负责课程X的部分老师调整到课程Y，调整之后公布课程X成绩的时间推迟一天，公布课程Y成绩的时间提前一天；每次操作产生A不愉快度。2.增加一部分老师负责学科Z，这将导致学科Z的出成绩时间提前一天；每次操作产生B不愉快度。上面两种操作中的参数X,Y,Z均可任意指定，每种操作均可以执行多次，每次执行时都可以重新指定参数。现在希望你通过合理的操作，使得最后总的不愉快度之和最小，输出最小的不愉快度之和即可
输入
第一行三个非负整数A,B,C，描述三种不愉快度，详见【问题描述】；
第二行两个正整数n,m(1≤n,m≤105)，分别表示学生的数量和课程的数量；
第三行n个正整数ti，表示每个学生希望的公布成绩的时间；
第四行m个正整数bi，表示按照原本的计划，每门课程公布成绩的时间。
1<=N,M,Ti,Bi<=100000,0<=A,B,C<=100000
输出
输出一行一个整数，表示最小的不愉快度之和。
样例输入
100 100 2
4 5
5 1 2 3
1 1 2 3 3
样例输出
6
题解
啥数据结构都没有的sb题
我TM考场上这道sb题才拿了60分真TM丧心病狂。
读懂题之后大概是NOIP普及组小学生都会。
直接枚举最终时间，求出同学的不愉快度，然后根据A和B的大小关系决定是否应该调整，以及应该调整多少。使用一个前缀和维护时间和，并用两个指针维护第一个大于当前时间的等待时间和公布时间。
代码一点也不难，时间复杂度是$O(n)$的。
另外bzoj中说的$C=10^{18}$有误，应为$10^{16}$。
#include <cstdio>#include <cstring>#include <algorithm>#define N 100010using namespace std;typedef long long ll;ll x[N] , y[N] , sx[N] , sy[N];int main(){ ll n , m , i , j , k , a , b , c , ans = 1ll << 62 , s1 , s2 , c1 , c2 , r = 0; scanf("%lld%lld%lld%lld%lld" , &a , &b , &c , &n , &m); for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &x[i]) , r = max(r , x[i]); for(i = 1 ; i <= m ; i ++ ) scanf("%lld" , &y[i]) , r = max(r , y[i]); sort(x + 1 , x + n + 1) , sort(y + 1 , y + m + 1); for(i = 1 ; i <= n ; i ++ ) sx[i] = sx[i - 1] + x[i]; for(i = 1 ; i <= m ; i ++ ) sy[i] = sy[i - 1] + y[i]; if(c >= 0x7fffffff) r = x[1]; for(i = 1 , j = k = 0 ; i <= r ; i ++ ) { while(j < n && x[j + 1] < i) j ++ ; while(k < m && y[k + 1] < i) k ++ ; s1 = i * k - sy[k] , s2 = sy[m] - sy[k] - i * (m - k) , c1 = c * (i * j - sx[j]); if(a >= b) c2 = s2 * b; else if(s1 >= s2) c2 = s2 * a; else c2 = s1 * a + (s2 - s1) * b; ans = min(ans , c1 + c2); } printf("%lld\n" , ans); return 0;}
【bzoj4868】[Shoi2017]期末考试 前缀和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。