首页 > 其他分享 >题解:洛谷P3745 期末考试(整数三分)

题解:洛谷P3745 期末考试(整数三分)

时间:2023-10-31 20:11:34浏览次数:48  
标签:洛谷 suan 题解 long return 愉快 val2 P3745 val1

题解:洛谷P3745 期末考试(整数三分)

题目传送门

题目大意:给出 \(n\) 个同学期望出成绩的时间限制 \(a_i\) 和 \(m\) 个学科公布成绩的初始时间 \(t_i\) ,1个同学每多等一天就产生 A 的不愉快度。问通过一番操作后最小的不愉快度之和是多少?

操作有两种:

1.让学科 X 的发布时间晚1天,学科 Y 的发布时间早1天,产生A的不愉快度。

2.让学科 Z 的发布时间早1天,产生 B 的不愉快度。

思路:

设 \(t\) 表示规定的所有学科公布成绩的时间期限,\(y\) 表示满足第 \(t\) 天时出所有成绩的最小不愉快度之和。

则 \(y\) 关于 \(t\) 的函数是一个下凹函数(或者说形状类似一个开口向上的抛物线吧)

考虑三分出最低点(三分的部分就是板子了)

考虑怎么算 \(y\) ,由两部分组成:(1)\(t_i<t\) 的所有同学的不愉快度 \(res\)(2)操作的不愉快度

操作的不愉快度有两种,一种是 A 的移大补小,一种是 B 的暴力删。

首先明确一点:不关心大的到底补到了哪个小的,小的最终具体时间也不关心,因为同学的不愉快度只跟上限 \(t\) 有关。下面对操作的不愉快度进行分讨:

(1)若 \(B \leq A\) , 那肯定只使用 B

(2)若 \(A < B\) , 记所有小于 t 的学科的时间可以提供的补过来的空缺为 val1 , 大于 t 的学科超过 t 的总时间为 val2

当 \(val1 \geq val2\),全用 A 操作

当 \(val1 < val2\),进行 val1 次 A 操作,再进行 (val2-val1)次 B 操作

注意三分的边界和退出条件,算 \(res,val1,val2\) 时可以 \(O(N)\) 遍历 \(a_i\) 和 \(t_i\) ,也可以先排序后记个前缀和,三分的时候二分查找一下 分界点 \(t\) 再两个数组中的位置,时间复杂度 \(O(log_3N*log_2N)\)(感觉有点抽象,具体细节看代码吧~),注意特判C很大的情况,不然要开unsigned long long。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define F(i,l,r) for(int i=l;i<=r;++i)
const int N=1e5+5;
const ll M=1e16;
int n,m,A,B,a[N],t[N];
ll C,s1[N],s2[N];
inline ll suan(int x){//限制所有学科天数不超过x 
	ll w1=upper_bound(t+1,t+m+1,x)-t-1,w2=lower_bound(a+1,a+n+1,x)-a-1,
		val1=x*w1-s2[w1],val2=(s2[m]-s2[w1])-(m-w1)*x,
		res=(w2*x-s1[w2])*C; 
		//val1:<x的w1天里有多少空缺
		//val2:超过x天的学科里要移动多少天过来(或者说理论上要多少空缺)
	if(A<B){
		if(val1>=val2) return A*val2+res;
		else return A*val1+B*(val2-val1)+res;
	}
	return val2*B+res;
}
int main(){
	scanf("%d%d%lld%d%d",&A,&B,&C,&n,&m); 
	F(i,1,n) scanf("%d",&a[i]); sort(a+1,a+n+1); F(i,1,n) s1[i]=s1[i-1]+a[i];
	F(i,1,m) scanf("%d",&t[i]); sort(t+1,t+m+1); F(i,1,m) s2[i]=s2[i-1]+t[i];
	if(C==1e16) return printf("%lld",suan(a[1])),0;//特判C很大的情况,不然要开unsigned long long 
	int l=0,r=t[m]+1,mid1,mid2;
	while(l+2<r){
		mid1=(2*l+r)/3,mid2=(l+2*r)/3;
		if(suan(mid1)>=suan(mid2)) l=mid1;
		else r=mid2;
	}
	printf("%lld",min({suan(l),suan(r),suan(l+1)}));
	return 0;
}

标签:洛谷,suan,题解,long,return,愉快,val2,P3745,val1
From: https://www.cnblogs.com/superl61/p/17801230.html

相关文章

  • 洛谷P3805 【模板】manacher
    题目链接:https://www.luogu.com.cn/problem/P3805manacher算法模板题。参考资料:https://oi-wiki.org/string/manacher/示例程序:#include<bits/stdc++.h>usingnamespacestd;constintmaxn=2.2e7+5;intn;chars[maxn/2],a[maxn];intp[maxn];voidinit(){......
  • P5404 [CTS2019] 重复 题解
    题目链接观察题目,我们发现直接计算是困难的,先构造单个合法的\(T\)分析其性质。为了构造出\(T\),先考虑构造时\(T\)时什么时候会出现不合法的情况,此时\(T\)会有一段和\(S\)相同的前缀,且这段前缀后面跟着的字符比\(S\)所跟的小。为了避免这种情况出现,我们需要在每次添......
  • 洛谷3281数数
    这一道题给我们最大的启示就是一定要学会固定数字!设\(Pow[i]=B^i\),\(f[i]=\sum_{k=0}^{i}{B^k}\)\(h[i]\)表示所有\(i\)位数字的所有前缀子串的和比如\(123456\)一共有\(6\)位,他的所有前缀子串为\(1,12,123,1234,12345,123456\),他的所有前缀子串和就是这六个数加起来,那么\(h[6......
  • CSPRO 历届题目与题解
    官方题目链接:http://118.190.20.162/\(\Huge目录\)201609201612201709202104202109202112202203202206202209202303202305202309\(\Huge\text{CSP201609}\)火车购票问题描述请实现一个铁路购票系统的简单座位分配算法,来处理一节车厢的座位分配。假设一节车厢......
  • AT_abc326_d ABC Puzzle 题解
    AT_abc326_dABCPuzzle题解看题事实上,即使在\(N=5\)的情况下,也只有\(66240\)个网格满足「每行/每列恰好包含一个A、B和C」。——官方题解其实看到这道题,就感觉是搜索,这很显然。但是我们会发现,最最最native的搜索,是\(4^{5\times5}=2^{50}\)的。感觉不大可过,但是......
  • AT_abc326_e Revenge of "The Salary of AtCoder Inc." 题解
    AT_abc326_eRevengeof"TheSalaryofAtCoderInc."题解一道简单的概率论+动态规划题目(然而我赛时没看这道题题意有一个长度为\(n\)的序列\(A\)、一个\(n\)面骰子,掷若干次骰子,如果这一次掷骰子的点数小于等于上一次的点数,则结束。定义这若干次掷骰子的总的结果为,每次......
  • AT_abc326_f Robot Rotation 题解
    AT_abc326_fRobotRotation题解经典问题,以前遇到过一个类似的问题:[ABC082D]FTRobot。建议对比着看一看这两道题,是两种不同的思路。(那一道题不用输出方案,因此可以用bitset优化;而此题需要输出方案,因此需要双向搜索。思路注意到每次只能「左转」和「左转」。所以,偶数次走......
  • AT_abc325_f Sensor Optimization Dilemma 题解
    AT_abc325_fSensorOptimizationDilemma题解Date20231025:修复手滑公式\(\min\)、\(\max\)写反了。动态规划。类似背包问题。朴素算法记\((x,y)\)表示使用\(x\)个(1)传感器、\(y\)个(2)号传感器。设\(f(t,i,j)\)表示覆盖前\(t\)个区间,使用\((i,j)\)传感......
  • AT_abc325_g offence 题解
    AT_abc325_goffence题解一道不难但是需要想一想的区间DP。有一个比较复杂的例子:ooofofxxx,简单的分析可知,一个of后面删除多少,与其前、后都有关,于是考虑区间DP。想到这里,其实问题已经解决一半了。状态设计设\(f(l,r)\)为闭区间\([l,r]\)经过操作之后的最小长度。注......
  • [CSP-S2020] 儒略日 题解
    [CSP-S2020]儒略日今儿终于做掉困扰多年的题目了,其实想好细节也不难。容易发现儒略历和格里高利历的润年判断方式不一样,并且中间有消失的十天,计算起来相当不方便。所以我们可以首先计算出\(-4713.1.1\)~\(1582.10.4\)会经过多少天,可以通过一天一天暴力跳的方法计算出需要\(......