【零件加工】

题目描述

工匠小 K 最近有 n 个零件需要加工。每个零件都需要 ti 天的时间来完成,每个零件每延迟一天加工都要缴纳一定的罚金 s。延迟的天数为从今天算起到该工作开始的那天,第一个零件加工没有罚金。现在小 K 想知道怎样安排加工顺序可以使他要交的罚金最少,最少是多少?
这个数可能会很大,请输出这个数对 m 取模后的结果。

输入格式

输入文件第一行为一个整数 n ,表示需要加工的零件总数。
第二行为一个整数 m ,表示答案要对 m 取模。
第 3~n+2 行,每行两个整数 ti 和 si

输出格式

输出仅一行,一个整数,表示小 K 最少要缴纳的罚金对 m 取模的结果。

样例数据 1

输入

2
100
2 33
33 2

输出

4

样例数据 2

输入

4
100
3 3
6 4
2 2
8 5

输出

81

备注

【样例1解释 】
先加工第一个,需要 2 天时间,再加工第二个。需要缴纳的罚金为 2×2=4 。

【样例2解释】
如果按照 1→2→3→4 的顺序进行加工,需要缴纳的罚金为:
0×3+3×4+(3+6)×2+(3+6+2)×5=85
最佳方案是 3→1→2→4,此时需要缴纳的罚金为:
0×2+2×3+(2+3)×4+(2+3+6)×5=81

【数据范围】
对于 40% 的数据,0<n≤10,000;0<ti,si≤10,000;
对于 80% 的数据,0<n≤100,000;0<ti,si≤2×109,0<m≤108
对于 100% 的数据,0<n≤100,000;0<ti,si≤2×109,0<m≤1018

这道题为啥是按t/s排序再贪心呢Poi~听了同学讲才豁然开朗,记到i的总时间为time[i],如果当前顺序的结果是ans,要把后面一项和前面一项交换的话,那么当前顺序的结果就变成了ans-(c[i].s*time[i]+c[i-1].s*time[i-1])+[c[i].s*(time[i]-c[i-1].time)+c[i-1].s*(time[i-1]+c[i].time) 化简得ans+c[i-1].s*c[i].time-c[i].s*c[i-1].time,要使最优解ans能被更新,即c[i-1].s*c[i].time-c[i].s*c[i-1].time<0,变形得c[i].time/c[i].s<c[i-1].time/c[i-1].s,然后就升序排一遍就完咯。

下面是代码:

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*