Solution for ZZQ's Catforces

ZZQ’s Catforces

idea by Nanako & bakapiano

prepared by bakapiano & zzq

题意

本题的背景为一个简化版的 CF 赛制，\(n\) 道题有一个初始分数 \(a[i]\)，掉分速度为 \(b[i]\)/每分钟 与与解题所需时间 \(t[i]\)，请你安排一个解题顺序使得得分：

最大。

题解

题目难度 medium-

注意到 \(\sum_{i=1}^{n}a_{i}\) 项与解题顺序无关，我们只需要最小化总掉分数即可。

首先我们任意安排一个解题顺序 \(p_{1},…,p_{n}\)，并尝试对当前得到的答案进行改进。设 \(p\) 数组中相邻的两项为 \(x,y(1 \leq x < y \leq n)\)，易知交换相邻两项对其他题目的得分没有影响(因为对于除 \(x,y\) 的任意题目 \(i\) 来说 \(\sum_{j=1}^{i}t_{j}\) 不变)，下面我们来推导在什么情况下交换 \(x,y\) 两项能使得答案变得更优。

首先设 \(pre = \sum_{j=1}^{x-1}t_{j}\)

设交换前 \(x,y\) 两项对答案的贡献：

交换后的贡献：

使答案更优的条件：

化简可得：

即:

设\(k_{i}=t_{i}/b_{i}\)，注意到当 \(k_{y}<k_{x}\) 时交换相邻两项会使答案更优，因此我们可以选择序列中 \(k_{i}\) 最小的一项并把它不断往前交换来使答案变的更优，然后选 \(k_{i}\) 次小的一项 … 重复上述操作直至序列中的 \(k_{i}\) 变得非递减，此使得到的排列便是最优解题顺序。

因此只需将所有题目按 \(t_{i}/b_{i}\) 的顺序排序，\(O(n)\) 计算答案即可，总复杂度 \(O(nlogn+n)\) 可以在规定时限内通过本题。

tag: 贪心 sort

标称

注意使用 \(double\) 计算斜率可能会造成精度误差，sort 时使用自定义比较函数即可避免这一问题。

#include <bits/stdc++.h> 

using namespace std;

typedef long long LL;

const int MAXN = 1e5+5;

/*----------head----------*/

int n;
struct pro{LL a,b,t;}p[MAXN];
LL s[MAXN],ans;
int main()
{
    scanf("%d",&n);
    fp(i,1,n)
        scanf("%lld%lld%lld",&p[i].a,&p[i].b,&p[i].t),ans+=p[i].a;
    sort(p+1,p+1+n,[](pro a,pro b){return a.t*b.b<b.t*a.b;});
    fp(i,1,n)
    {
        s[i]=s[i-1]+p[i].t;
        ans-=s[i]*p[i].b;
    }
    printf("%lld\n",ans);
    return 0;
}