BZOJ4868: [Shoi2017]期末考试
2018-06-17 20:59:35来源:未知 阅读 ()
Submit: 936 Solved: 426
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
4 5
5 1 2 3
1 1 2 3 3
Sample Output
由于调整操作产生的不愉快度太大,所以在本例中最好的方案是不进行调整; 全部
5 的门课程中,最慢的在第 3 天出成绩;
同学 1 希望在第 5 天或之前出成绩,所以不会产生不愉快度;
同学 2 希望在第 1 天或之前出成绩,产生的不愉快度为 (3 - 1) * 2 = 4;
同学 3 希望在第 2 天或之前出成绩,产生的不愉快度为 (3 - 2) * 2 = 2;
同学 4 希望在第 3 天或之前出成绩,所以不会产生不愉快度;
不愉快度之和为 4 + 2 = 6 。
HINT
存在几组数据,使得C = 10 ^ 16
Source
黑吉辽沪冀晋六省联考
考场上还是静不下心来
总感觉这题是个dp
然后直接弃掉了。
其实还是挺简单的。
我们钦定一个试卷被批完的最晚时间
然后通过二分+前缀和计算出学生的不愉快度
再利用二分+后缀和计算出让最后一个被批完的试卷的时间满足要求的不愉快的
两者求和取最小值就可以了
这道题的关键是看出学生不满意度和试卷被批完的时间之间的单调关系
然后要想到枚举时间
#include<cstdio> #include<cmath> #include<algorithm> #define int unsigned long long using namespace std; const int MAXN=1e5+10; const int INF=1e19; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int A,B,C; int N,M; int t[MAXN],b[MAXN]; int sumt[MAXN],sumb[MAXN];//t的前缀与b的后缀 int limit,ans=INF; main() { #ifdef WIN32 freopen("a.in","r",stdin); #endif A=read();B=read();C=read(); N=read();M=read(); for(int i=1;i<=N;i++) t[i]=read(); for(int i=1;i<=M;i++) b[i]=read(),limit=max(limit,b[i]); sort(t+1,t+N+1); sort(b+1,b+M+1); for(int i=1;i<=N;i++) sumt[i]=t[i]+sumt[i-1]; for(int i=M;i>=1;i--) sumb[i]=b[i]+sumb[i+1]; for(int i=1;i<=limit;i++) { int l=1,r=N,ans1=0,ans2=0,now=0; while(l<=r) { int mid=l+r>>1; if(t[mid]<i) ans1=mid,l=mid+1; else r=mid-1; } l=1,r=M; while(l<=r) { int mid=l+r>>1; if(b[mid]>i) ans2=mid,r=mid-1; else l=mid+1; } if(ans1!=0) now+=(ans1*i-sumt[ans1])*C; if(ans2!=0) { int need=(sumb[ans2]-(M-ans2+1)*i); if(A>=B) now+=need*B; else { int have=(ans2-1)*i-(sumb[1]-sumb[ans2]); if(have>=need) now+=need*A; else now+=have*A+(need-have)*B; } } ans=min(ans,now); } printf("%lld",ans); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 中国大学MOOC-陈越、何钦铭-数据结构-2016秋期末考试 2018-06-18
- BZOJ4872: [Shoi2017]分手是祝愿 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash