F题 #智乃的算法竞赛群友#

题目描述

怎么排列才能最快乐？

思路

考试完没多久改出来了，我们想到只有三种情况，qcjjkkt、td和qcjjkktd，我们失败地没有注意到以n=56*k为讨论依据，想到从单位快乐值入手，但是发现会有漏洞，比如长度为8的字符，使用4个td和一个qcjjkktd哪个划算不好判断，最后多余的字符可能性也可能造成结果错误。因此我们这样想：

设放置了k个"qcjjkkt"，其中t个后面跟了'd'（即变成组合），则总长度为7k+t，同时 获得t个额外的"td"。剩余空间可放s个独立的"td"，每个占2长度。总快乐值为ak + b(t + s)，满足7k + t + 2s ≤ n；

对于一个固定的k，优先将剩余长度用于把普通"qcjjkkt”变成组合比放独立"td"更优。因此：

若n-7k ≥ k(即8k ≤ n)，则可将所有k个都变成组合，剩余n - 8k长度放独立"td"，总"td"个数为k + (n - 8k) / 2 = (n - 6k) / 2;

否则，只能将部分变成组合，即t = n - 7k,无独立 "td"，总"td"个数为 n − 7k。

因此快乐值可视为关于k的函数，当k ≤ n / 8时，斜率为a - 3b，当k ＞ n / 8时，斜率为a - 7b；根据图像可知最大值只可能出现在区间端点，即k = 0、k = n / 7、k = n / 8、k = n / 8 + 1（若不超过n / 7）。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'

ll calc(ll n, ll a, ll b, ll k) {
    ll m;
    if (n-7*k >= k) {
        m = (n - 6*k)/2;
    } else {
        m = n-7*k;
    }
    return a*k+b*m;
}

int main(){
    int t;
    cin >> t;
    while (t--){
        ll n, a, b;
        cin >> n >> a >> b;
        
        ll k0 = 0;
        ll k1 = n/7;
        ll k2 = n/8;
        ll k3 = k2+1;
        if (k3>k1) k3 = k1;
        
        ll ans = 0;
        ans = max(ans, calc(n, a, b, k0));
        ans = max(ans, calc(n, a, b, k1));
        ans = max(ans, calc(n, a, b, k2));
        if (k3 <= k1 && k3 >= 0) {
            ans = max(ans, calc(n, a, b, k3));
        }
        cout << ans << '\n';
    }
    return 0;
}