Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 8126 | Accepted: 2064 |
Description
It is very hard to wash and especially to dry clothes in winter. But Jane is a very smart girl. She is not afraid of this boring process. Jane has decided to use a radiator to make drying faster. But the radiator is small, so it can hold only one thing at a time.
Jane wants to perform drying in the minimal possible time. She asked you to write a program that will calculate the minimal time for a given set of clothes.
There are n clothes Jane has just washed. Each of them took ai water during washing. Every minute the amount of water contained in each thing decreases by one (of course, only if the thing is not completely dry yet). When amount of water contained becomes zero the cloth becomes dry and is ready to be packed.
Every minute Jane can select one thing to dry on the radiator. The radiator is very hot, so the amount of water in this thing decreases by k this minute (but not less than zero — if the thing contains less than k water, the resulting amount of water will be zero).
The task is to minimize the total time of drying by means of using the radiator effectively. The drying process ends when all the clothes are dry.
Input
The first line contains a single integer n (1 ≤ n ≤ 100 000). The second line contains ai separated by spaces (1 ≤ ai ≤ 109). The third line contains k (1 ≤ k ≤ 109).
Output
Output a single integer — the minimal possible number of minutes required to dry all clothes.
Sample Input
sample input #1 3 2 3 9 5 sample input #2 3 2 3 6 5
Sample Output
sample output #1 3 sample output #2 2
题意:
给出 N (1 ~ 100000),代表有 N 件衣服,后给出每件衣服的湿度 ai(1 ~ 10 ^ 9),后给出 K (1 ~ 10 ^ 9)代表烘干机的烘干速度是 K,平常风干的话是 1。烘干机每次只能对一件衣服,输出当所有衣服都干了的最少时间。
思路:
二分搜索。搜索烘干时间 t 。找最小值,所以左开右闭,t 的范围是 (0 ,max_ai ] 。假设烘干的时间为 t ,那么就要求所有衣服都必须要在 t 时间内变干:
若 ai <= t , 直接风干就好,不需要烘干机;
若 ai > t ,则需要烘干机,因为每次烘干机只对一件衣服,所以要最大利用烘干机的次数才行,对于每件衣服来说,就需要求一个最少利用烘干机的时间数。
设风干的时间为 F,烘干机的时间为 H,所以 F + H = t ;对于 ai,F + H * k >= ai,两条式子合并消掉 F ,就能得到 H >= ( ai - t ) / (k - 1) ,对得数向上取整便求出最少的 H 。将所有衣服的 H 相加起来可以得三种情况:
若 H < t ,说明在规定的时间 t 内能把全部衣服给烘干,那么应该继续往小的搜,所以搜 ( l , t ];
若 H > t ,说明在规定的时间 t 内不能把全部衣服烘干,那么应该继续往大的搜,所以搜 ( t , r ];
若 H == t ,说明在规定的时间 t 内能把全部衣服烘干,但是要求找到的是最少的时间,所以要继续往小的搜,所以搜 (l , t ]。
注意点:
1.注意搜索边界,是从 0 到 max_ai,而不是 min_ai 到 max_ai;
2.注意推到公式的条件,分母为k - 1,所以 k - 1 != 0,所以当 k == 1 的时候要单独拿出来讨论;
3.注意公式的正确推到过程;
4.二分搜索边界要开 long long 型,不然会WA;
AC:
#include <cstdio> #include <algorithm> const int INF = 100000005; using namespace std; typedef long long ll; int n, max_t, k; int clo[100005]; bool C(ll t) { ll ans = 0; for (int i = 0; i < n; ++i) { if (clo[i] > t) { ll left = clo[i] - t; ans += (left / (k - 1) + (left % (k - 1) != 0)); } } return ans <= t; } void solve() { ll l = 0, r = max_t; while(r - l > 1) { ll mid = l + (r - l) / 2; if (C(mid)) r = mid; else l = mid; } printf("%lld\n",r); } int main() { //freopen("test.in", "r", stdin); scanf("%d", &n); max_t = -1; for (int i = 0; i < n; ++i) { scanf("%d", &clo[i]); max_t = max(max_t,clo[i]); } scanf("%d", &k); if(k == 1) printf("%d\n",max_t); else solve(); return 0; }
相关推荐
Effect of freeze-drying and production process on the chemical composition and fatty acids profile of avocado pulp
一篇关于太阳能热发电的论文,与有机郎肯循环有关。
真空干燥是制药和食品工业中常用于除去潮湿粉末中的水分或有机溶剂的化工工艺。设计真空干燥系统时,工程师会在确保产品高质量的同时,尽可能地缩短干燥过程所需的时间。该模型研究 Nutsche 过滤干燥机中的真空干燥...
烘干时间对锑掺杂二氧化锡涂覆钛基底电极的影响,王云海,周喆,采用浸渍涂覆法在不同的烘干时间下制备了锑掺杂二氧化锡涂覆钛电极。研究了不同的烘干时间对电极活性、形貌、结晶度和组成的影响
超临界流体干燥法制备纳米铈锰气凝胶,张慧强,YU Gao-qi,以碳酸铈和硝酸锰为原料,利用溶胶-凝胶法制备纳米铈锰气凝胶,利用XRD、TEM、红外分析和热分析对其进行表征,用NO和CO的反应来测试�
水稻花后土壤干旱对籽粒中脱落酸、乙烯和抗氧化系统的影响及其与籽粒灌浆的关系,张耗,刘凯,本研究以2个水稻品种为材料,种植于盆钵,自花后9天至成熟设置3个土壤水分处理,分别是保持水层灌溉(WW)、土壤轻度落...
A mathematical model of drying and preheating processes in a traveling grate was presented based on the laws of mass,momen-tum,heat transfer,and drying semiempirical relations. A field test was ...
Microstructure and compressive behavior of lamellar Al2O3p/Al composite prepared by freeze-drying and mechanical-pressure infiltration method
SYMBOLSaActiveareaperunitvolume,sq.fi.percu..ft.AInterfacialarea,acrosswhichdiffusionorheattransferisoccur-ing,sq.ft.BxEquivalentfilmthickness,ft.GAirrate,fo.perhr.hHeattransfercoefficient,B.t.u.persq...
Our research focused on the analysis of concrete deterioration mechanism under the coupling effects of flexural load, cyclic wetting and drying, and sulfate. The relative dynamic modulus of elasticity...
Freeze drying and frozen preservation way was used to preserve a moderately thermophilic culture for bioleaching of chalcopyrite concentrate. After preservation of 15 months, the cell viability rate ...
In the present work, the feasibility of NIRS for monitoring the moisture content of human coagulation factor VIII (FVIII) in freeze-drying process was investigated. A partial least squares regression...
在一行中输出此人在第N天中是“Fishing”(即“打鱼”)还是“Drying”(即“晒网”),并且输出“in day N”。 输入样例1: 103 结尾无空行 输出样例1: Fishing in day 103 结尾无空行 输入样例2: 34 输出样例2...
matlab代码续行干燥土壤和沙漠生物结壳的力学模型 该存储库包含动态水合作用条件下的沙漠生物地壳模型(DBM)的源代码。 这项工作是在静态水合条件下DBM的延续[1]。 您可以在找到该工作的主要代码。...
drying dishes # 10:09 # 10:12 dishes # 10:19 # 10:21 drying dishes # 10:22 # 10:26 dishes # 10:27 # 10:33 lunch # 12:13 # 13:20 dev # 13:39 # 16:41 " lookup = " drying dishes #housework #kitchen #...
For the purpose of exploring the characteristics of zeolite in drying purple potatoes under the vacuum condition, zeolite was used in the vacuum drying system to form a new kind of drying system which...
引入水泥窑窑尾废气,利用废气余热进行物料干燥、发电等,并对余热利用后的废气进行净化处理的系统。3.4烘干机、烘干磨、煤磨及冷却机 dryer,drying an
欧姆龙 F03-16SF漏液检测器手册pdf,The sheath becomes transparent to reveal the red inner sheath if liquid leakage occurs, thereby enabling ... After drying, the Sensing Band color will return to white.
摘 要:高效钢包烘烤装置采用旋流二...烘包曲线中图分类号:TF341.9 文献标识码:B 文章编号:1004-4620(2003)01-0064-02 Development and Application of the High Efficient Ladle Drying System SUN De-min,DOU