38870

期末考试:单峰函数三分

Description

<blockquote>有n位同学,每位同学都参加了全部的m门课程的期末考试,都在焦急的等待成绩的公布。

第i位同学希望在第t<sub>i</sub>天或之前得知所有课程的成绩。如果在第t<sub>i</sub>天,有至少一门课程的成绩没有公布,他就会等待最后公布成绩的课程公布成绩,每等待一天就会产生C不愉快度。

对于第i门课程,按照原本的计划,会在第b<sub>i</sub>天公布成绩。

有如下两种操作可以调整公布成绩的时间:

<ol><li>将负责课程i的部分老师调整到课程 j ,调整之后公布课程i成绩的时间推迟一天,公布课程j成绩的时间提前一天;每次操作产生A不愉快度。</li> <li value="2">增加一部分老师负责学科i,这将导致学科i的出成绩时间提前一天;每次操作产生B不愉快度。</li> </ol>

上面两种操作中的参数i,j均可任意指定,每种操作均可以执行多次,每次执行时都可以重新指定参数。

现在希望你通过合理的操作,使得最后总的不愉快度之和最小,输出最小的不愉快度之和即可。

</blockquote>

Input

<blockquote>

第一行三个非负整数XYZ,描述三种不愉快度,详见【题目描述】;
第二行两个正整数n,m,分别表示学生的数量和课程的数量;
第三行 个正整数t<sub>i</sub>,表示每个学生希望的公布成绩的时间;
第四行 个正整数b<sub>i</sub>,表示按照原本的计划,每门课程公布成绩的时间。

</blockquote>

Output

<blockquote>

输出一行一个整数,表示最小的不愉快度之和。

</blockquote>

Sample Input 1

<blockquote> 100 100 2 4 5 5 1 2 3 1 1 2 3 3 </blockquote>

Sample Output 1

<blockquote>6</blockquote>

Sample Input 2

<blockquote> 3 5 4 5 6 1 1 4 7 8 2 3 3 1 8 2 </blockquote>

Sample Output 2

<blockquote>33</blockquote>

Hint

<blockquote>

A,B<=1e9,C<=1e16,n,m,b<sub>i</sub>,t<sub>i</sub><=1e5

</blockquote>

刚向cbx颓标签做完宅男计划完之后做的这道题,所以做得比较水。

但是这类三分的题还是需要写一个题解来记录一下的。

这题其实看了标签之后就没什么意思了?

首先,最终对答案产生影响的就是出分最晚的那一科的时间,我们把这个作为费用函数的参数。

呃,比较显然,如果你把出成绩的天数推迟地太晚,那么学生受不了不满意度会很高。

但是如果你让老师加班出分太早,那么老师受不了不满意度也会很高。

所以可以嗅到单峰函数的味道了吗?

暂时不会证明它的确是一个严格的单峰函数。网上也没有。。。

暂且这么理解。反正也没有反例。实在不行你打一个模拟退火。先继续让我讲下去。。。

那么现在我们就可以三分答案了,每次用O(n+m)的复杂度统计总的不满意度,三分即可。

至于怎么统计,还好吧?统计那些出分早的学科一共能派出多少老师支援其它学科设为a,再统计出分晚的学科达到那个天数需要多少援助为b。

那么我们就是要用a个价格为A的物品,无数个价格为B的物品,买b件的最小代价。

稍微分类讨论一下不成Question。

然后对于已经确定的天数,再枚举每一个同学统计不满意度,这也不用多说。

那么就没什么Question了吧?

1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 #define int long long 5 int a,b,c,n,m,w[100005],re[100005]; 6 long double Q(int d){ 7 int up=0,down=0;long double fee=0; 8 for(int i=1;i<=m;++i)if(re[i]>d)down+=re[i]-d;else up+=d-re[i]; 9 if(a<b)fee+=1.0*min(up,down)*a+max(0ll,down-up)*b;else fee=1.0*down*b; 10 for(int i=1;i<=n;++i)fee+=1.0*max(0ll,d-w[i])*c; 11 return fee; 12 } 13 signed main(){ 14 scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&n,&m); 15 for(int i=1;i<=n;++i)scanf("%lld",&w[i]); 16 for(int i=1;i<=m;++i)scanf("%lld",&re[i]); 17 int l=1,r=100000,ml,mr,lans,rans; 18 while(l<r-2)if(Q(l+r>>1)<Q((l+r>>1)+1))r=(l+r>>1)+1;else l=l+r>>1; 19 printf("%.0Lf\n",min(Q(l+1),min(Q(l),Q(r))));//printf("%lld %lld\n",l,r); 20 } 但是还没有完

好像还有一种做法,更加草率。

因为统计不满意度时,这其实是一个序列上的Question,前驱后继前缀和什么的,可以用数据结构/STL什么的来达到log复杂度来统计答案的效果。

好像需要的操作也就是查b数组里有多少数比mid大,它们的和是多少,小的同理。sort后前缀和与lower_bound可以解决。

以及要查t数组里比mid大的和它们的和,依旧前缀和。然后好像就没了,的确可以log?

没有实测,可能是我在yy?

那么就可以O(1e6)枚举所有的天数了,就没有三分答案了,直接取min就行。这个相较于那个没有被证明的单峰函数更可靠一些?

但是我没有打。。。

哦对了值得注意的一点是运算过程中那个C那么大很可能会爆long long,推荐用double。

因为无论是什么数据答案都不会超过long long,所以用double计算后如果太大直接舍弃就好,否则再细算。

来源:博客园

作者:DeepinC

链接:https://www.cnblogs.com/hzoi-DeepinC/p/11425615.html

Recommend