2019南京网络赛 I Washing clothes —— 神级思维

本文主要是介绍2019南京网络赛 I Washing clothes —— 神级思维，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $n$ 个人要洗衣服，一台洗衣机
    手洗为 $y$ 分钟，机洗为 $x$ 分钟
    问 $x$ 从 $1$ 到 $y$ 的所有最小时间？？？

解题思路：

    考虑枚举每一个人对答案的影响
    对于一个特定的 $x$，答案肯定是从一个人开始后面都用洗衣机
    为什么呢？？假设是这样的策略序列：

y	y	y	x	x	x	x
$t_1$	$t_2$	$t_3$	$t_4$	$t_5$	$t_6$	$t_7$

    表示从 $t_4$ 开始都用机洗，且影响最终答案的人是第四个人（和第三个人）
    为什么后面不能再有人用 $y$ 了？

y	y	y	x	x	y	x
$t_1$	$t_2$	$t_3$	$t_4$	$t_5$	$t_6$	$t_7$

    这样就变成了第六个人影响答案了，或者说：
    如果第六个人用 $y$ 会使得答案变小，那么我在枚举第七个人同样会计算出答案
    如果第六个人用 $y$ 会使得答案变大，那么就不是最佳策略

    所以如果从第 $i$ 个人开始用洗衣机，答案就是
    $max(t_{i-1}+y,ma{x}_{j=i}^N{t}_j+(N-j+1)\times x)$
    设 $f(i)=t_{i-1}$，是个单调递增函数
    设 $g(i)=ma{x}_{j=i}^N{t}_j+(N-j+1)\times x)$，是个单调递减函数
    则 $max(f(i),g(i))$ 是一个凸函数

    那么问题就变为了求这个函数的极小值，我们设 $p=y/x$，$y=p\times x$
    且极小值点一定在 $n-p+1$ ！！！！！！
    下面开始证明：

	$f(i)$	$g(i)$
$n-p+2$	$t_{n-p+1}+y$	$ma{x}_{j=n-p+2}^N{t}_j+(N-j+1)\times x)$
$n-p+1$	$t_{n-p}+y$	$ma{x}_{j=n-p+1}^N{t}_j+(N-j+1)\times x)$
$n-p$	$t_{n-p-1}+y$	$ma{x}_{j=n-p}^N{t}_j+(N-j+1)\times x)$

    

$t_{n-p}+y=t_{n-p}+p\times x$       $＜$      $t_{n-p}+(p+1)\times x$       $\le$      $ma{x}_{j=n-p}^N{t}_j+(N-j+1)\times x)$

    即 $f(n-p+1)\le g(n-p)$
    也就说明在 $n-p+1$ 这个点之前， $f(i)$ 一直小于 $g(i)$
    也就说明极小值点一定在 $n-p+1$ 之后！

---

    当 $i＞n-p+1，n-i+1＜p$
    对于 $g(i)$ 而言，$g(i)=max(t_i+(n-i+1)\times x,g(i+1))$
    

$t_i+(n-i+1)\times x$      $＜$      $t_i+px$       $=$       $t_i+y$       $=$      $f(i+1)$
    即 $max(f(i+1),g(i+1))\ge g(i)$， 且 $f(i+1)＞f(i)$
    也就说明极小值点一定在 $n-p+1$ 之前！

---

    也就证明了极小值点一定在 $n-p+1$
    那么对于每个 $x$ 而言，只需要枚举 $ma{x}_{j=n-p+1}^N{t}_j+(N-j+1)\times x)$，也就是 $p=y/x$ 次

    时间复杂度：$O({\sum }_{x=1}^y\frac{y}{x})=$ $O(ylogy)$

---

    给的题解里要用李超树维护新加的线段，有空来补…

核心：看傻了

#include<bits/stdc++.h>
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
int n, y, t[maxn];int main() {while(~scanf("%d%d", &n, &y)) {for(int i=1; i<=n; i++) scanf("%d", t+i);sort(t+1, t+n+1);for(int x=1; x<=y; x++) {ll p = min(n, y / x), ans = 0;if(n-p) ans = t[n-p] + y;for(int i=n; i>n-p; i--)ans = max(ans, t[i] + 1ll*(n-i+1)*x);printf("%d%c", ans, x<y ? ' ' : '\n');}}
}

这篇关于2019南京网络赛 I Washing clothes —— 神级思维的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---