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

2023-11-02 10:48

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

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

题目大意:

     n n n 个人要洗衣服,一台洗衣机
    手洗为 y y y 分钟,机洗为 x x x 分钟
    问 x x x 1 1 1 y y y 的所有最小时间???

解题思路:

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

yyyxxxx
t 1 t_1 t1 t 2 t_2 t2 t 3 t_3 t3 t 4 t_4 t4 t 5 t_5 t5 t 6 t_6 t6 t 7 t_7 t7

    表示从 t 4 t_4 t4 开始都用机洗,且影响最终答案的人是第四个人(和第三个人)
    为什么后面不能再有人用 y y y 了?

yyyxxyx
t 1 t_1 t1 t 2 t_2 t2 t 3 t_3 t3 t 4 t_4 t4 t 5 t_5 t5 t 6 t_6 t6 t 7 t_7 t7

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

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

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

f ( i ) f(i) f(i) g ( i ) g(i) g(i)
n − p + 2 n-p+2 np+2 t n − p + 1 + y t_{n-p+1}+y tnp+1+y m a x j = n − p + 2 N t j + ( N − j + 1 ) × x ) max ^N _{j=n-p+2}t_j + (N-j+1)\times x) maxj=np+2Ntj+(Nj+1)×x)
n − p + 1 n-p+1 np+1 t n − p + y t_{n-p}+y tnp+y m a x j = n − p + 1 N t j + ( N − j + 1 ) × x ) max ^N _{j=n-p+1}t_j + (N-j+1)\times x) maxj=np+1Ntj+(Nj+1)×x)
n − p n-p np t n − p − 1 + y t_{n-p-1}+y tnp1+y m a x j = n − p N t j + ( N − j + 1 ) × x ) max ^N _{j=n-p}t_j + (N-j+1)\times x) maxj=npNtj+(Nj+1)×x)

    

t n − p + y = t n − p + p × x t_{n-p}+y = t_{n-p}+p\times x tnp+y=tnp+p×x       < <       t n − p + ( p + 1 ) × x t_{n-p} + (p+1)\times x tnp+(p+1)×x       ≤ ≤       m a x j = n − p N t j + ( N − j + 1 ) × x ) max ^N _{j=n-p}t_j + (N-j+1)\times x) maxj=npNtj+(Nj+1)×x)

    即 f ( n − p + 1 ) ≤ g ( n − p ) f(n-p+1) ≤ g(n-p) f(np+1)g(np)
    也就说明在 n − p + 1 n-p+1 np+1 这个点之前, f ( i ) f(i) f(i) 一直小于 g ( i ) g(i) g(i)
    也就说明极小值点一定在 n − p + 1 n-p+1 np+1 之后!


    当 i > n − p + 1 , n − i + 1 < p i >n-p+1,n-i+1<p inp+1ni+1p
    对于 g ( i ) g(i) g(i) 而言, g ( i ) = m a x ( t i + ( n − i + 1 ) × x , g ( i + 1 ) ) g(i) = max(t_i+(n-i+1)\times x, g(i+1)) g(i)=max(ti+(ni+1)×x,g(i+1))
    

t i + ( n − i + 1 ) × x t_i+(n-i+1)\times x ti+(ni+1)×x      < <       t i + p x t_i+px ti+px       = = =       t i + y t_i+y ti+y       = = =      f ( i + 1 ) f(i+1) f(i+1)

    即 m a x ( f ( i + 1 ) , g ( i + 1 ) ) ≥ g ( i ) max(f(i+1),g(i+1)) ≥ g(i) max(f(i+1),g(i+1))g(i), 且 f ( i + 1 ) > f ( i ) f(i+1) >f(i) f(i+1)f(i)
    也就说明极小值点一定在 n − p + 1 n-p+1 np+1 之前!


    也就证明了极小值点一定在 n − p + 1 n-p+1 np+1
    那么对于每个 x x x 而言,只需要枚举 m a x j = n − p + 1 N t j + ( N − j + 1 ) × x ) max ^N _{j=n-p+1}t_j + (N-j+1)\times x) maxj=np+1Ntj+(Nj+1)×x),也就是 p = y / x p = y / x p=y/x

    时间复杂度: O ( ∑ x = 1 y y x ) = O(\sum_{x=1}^y \frac{y}{x}) = O(x=1yxy)= O ( y l o g y ) O(ylogy) 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 —— 神级思维的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/330076

相关文章

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

ASIO网络调试助手之一:简介

多年前,写过几篇《Boost.Asio C++网络编程》的学习文章,一直没机会实践。最近项目中用到了Asio,于是抽空写了个网络调试助手。 开发环境: Win10 Qt5.12.6 + Asio(standalone) + spdlog 支持协议: UDP + TCP Client + TCP Server 独立的Asio(http://www.think-async.com)只包含了头文件,不依

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码

poj 3181 网络流,建图。

题意: 农夫约翰为他的牛准备了F种食物和D种饮料。 每头牛都有各自喜欢的食物和饮料,而每种食物和饮料都只能分配给一头牛。 问最多能有多少头牛可以同时得到喜欢的食物和饮料。 解析: 由于要同时得到喜欢的食物和饮料,所以网络流建图的时候要把牛拆点了。 如下建图: s -> 食物 -> 牛1 -> 牛2 -> 饮料 -> t 所以分配一下点: s  =  0, 牛1= 1~

poj 3068 有流量限制的最小费用网络流

题意: m条有向边连接了n个仓库,每条边都有一定费用。 将两种危险品从0运到n-1,除了起点和终点外,危险品不能放在一起,也不能走相同的路径。 求最小的费用是多少。 解析: 抽象出一个源点s一个汇点t,源点与0相连,费用为0,容量为2。 汇点与n - 1相连,费用为0,容量为2。 每条边之间也相连,费用为每条边的费用,容量为1。 建图完毕之后,求一条流量为2的最小费用流就行了

poj 2112 网络流+二分

题意: k台挤奶机,c头牛,每台挤奶机可以挤m头牛。 现在给出每只牛到挤奶机的距离矩阵,求最小化牛的最大路程。 解析: 最大值最小化,最小值最大化,用二分来做。 先求出两点之间的最短距离。 然后二分匹配牛到挤奶机的最大路程,匹配中的判断是在这个最大路程下,是否牛的数量达到c只。 如何求牛的数量呢,用网络流来做。 从源点到牛引一条容量为1的边,然后挤奶机到汇点引一条容量为m的边

配置InfiniBand (IB) 和 RDMA over Converged Ethernet (RoCE) 网络

配置InfiniBand (IB) 和 RDMA over Converged Ethernet (RoCE) 网络 服务器端配置 在服务器端,你需要确保安装了必要的驱动程序和软件包,并且正确配置了网络接口。 安装 OFED 首先,安装 Open Fabrics Enterprise Distribution (OFED),它包含了 InfiniBand 所需的驱动程序和库。 sudo

【机器学习】高斯网络的基本概念和应用领域

引言 高斯网络(Gaussian Network)通常指的是一个概率图模型,其中所有的随机变量(或节点)都遵循高斯分布 文章目录 引言一、高斯网络(Gaussian Network)1.1 高斯过程(Gaussian Process)1.2 高斯混合模型(Gaussian Mixture Model)1.3 应用1.4 总结 二、高斯网络的应用2.1 机器学习2.2 统计学2.3

网络学习-eNSP配置NAT

NAT实现内网和外网互通 #给路由器接口设置IP地址模拟实验环境<Huawei>system-viewEnter system view, return user view with Ctrl+Z.[Huawei]undo info-center enableInfo: Information center is disabled.[Huawei]interface gigabit

(南京观海微电子)——GH7006 Application Note

Features ⚫ Single chip solution for a WXGA α-Si type LCD display ⚫ Integrate 1200 channel source driver and timing controller ⚫ Display Resolution: ◼ 800 RGB x 480 ◼ 640 RGB x 480 ⚫ Display int