[已解决]Python：每日一题 300

塔利班

1. def f300(pages,k):
   
2.     if not pages:
   
3.         return 0
   
4.     l=len(pages)
   
5.     if k>=l:
   
6.         return max(pages)
   
7.     elif k==1:
   
8.         return sum(pages)
   
9.     else:
   
10.         t=sum(pages)//k
    
11.         i=m=s=0
    
12.         for e in pages:
    
13.             if e>2*(t-s) and i<k-1:
    
14.                 i+=1
    
15.                 m=max(s,m)
    
16.                 s=0
    
17.             s+=e
    
18.         return max(s,m)

复制代码

这次应该没错了，且是On

_2_

kinkon 发表于 2020-1-5 15:22
手机码字，也不知道有没缩进错误和码错代码
def f300(pages:list,k:int):
    ln=range(pages)

有缩进错误

zltzlt

_2_ 发表于 2020-1-5 16:32
有缩进错误

并没有：

_2_

_2_ 发表于 2020-1-5 16:32
有缩进错误

only 两个空格

_2_

1. ln=range(pages)

复制代码

这能这么用吗？

zltzlt

塔利班 发表于 2020-1-5 16:26
这次应该没错了，且是On

还是有错。

输入：

1. pages = [8720,1593,4278,1018,9515,5536,8694,869,8423,9920,3425,9689,9908,1404,8371,6019,7531,943,9280,8058,1445,7485,9223,5067,736,6065,1724,3269,130,1297,1701,5585,1209,5901,3760,3216,5307,8534,9575,7135,1251,3531,5162,7432,8559,2024,9738,2621,7926,3865,9904,4763,2031,4561,5870,6033,6442,6405,9886,8455,8970,6746,7923,5222,274,3875,5821,816,3459,9916,9447,4252,1871,5784,8272,9526,1531,5647,6676,2416,6281,7878,4382,5376,3618,1158,3717,5573,5602,5919,7579,6628,929,6897,8324,8657,8342,8190,7384,2466,8715,2499,9144,7349,3236,2852,4613,1917,5345,9288,9205,3363,5008,156,4716,6924,3490,605,3872,577,5393,7941,7390,7042,8242,5376,5939,3910,4727,4053,4850,5531,2658,3876,9379,6157,7544,2845,5499,459,3119,2984,5567,5706,1507,5971,8369,8177,5985,1215,8258,2925,9193,7999,334,4761,2586,7770,195,5804,3898,7214,6625,2975,4078,5441,9944,4161,9225,7012,6383,4441,4474,7030,7292,6938,48,6253,4707,2078,8449,7011,65,7205,4841,2066,5097,3875,6431,2626,6325,789,5047,324,3528,1325,2443,281,3094,1908,9686,8720,9310,6817,1856,2137,7718,1180,5988,8766,3408,8439,2555,2214,2678,1991,7393,6323,9586,8430,3298,9828,9386,5406,12,7231,8808,3655,208,6314,246,6279,9172,9980,5042,5659,7293,5428,2789,6454,2887,5948,6895,847,1443,754,4889,9509,2008,7163,5297,3845,7290,636,1900,7035,2718,6348,9216,2577,9852,3935,412,6605,3786,2158,9280,9835,8941,2575,2868,9006,6860,8101,3714,7940,268,8199,5597,9898,982,2825,5125,9865,3008,7575,8914,7330,4410,2063,214,3625,1588,8894,7882,503,8305,2701,8230,1336,1946,1318,2314,7348,3387,670,3682,7588,9411,3812,2509,1106,6148,9162,3716,9041,4980,2057,251,1778,7969,2805,5764,1266,6531,5219,8550,1921,9687,8127,826,4642,9398,4097,512,3296,2618,5132,2890,3471,2757,6336,5853,789,980,9109,5240,9449,758,8198,3420,4998,4239,995,5805,1997,9124,1265,694,8920,1770,3965,9473,6176,9059,6479,3190,8678,7136,9005,6420,1664,8229,8838,6959,8267,3220,8445,7166,7999,6727,4942,8306,5704,2005,9106,6139,1954,8219,1707,150,9456,2125,9215,6515,3446,2391,5560,2031,4940,7600,5852,6911,6330,571,1691,4217,9403,8555,4183,7995,8398,7931,7509,127,2514,7970,47,7970,2914,9730,86,12,723,4736,8464,1108,5422,5102,57,3366,9275,7030,7054,1230,9787,9268,8967,2653,1453,5486,7214,3899,9681,315,965,7969,8778,7791,2656,3646,988,261,3800,1317,9497,386,243,7713,9333,1563,9973,4759,4799,6150,2865,5293,9948,8505,1550,1240,321,2195,1521,2108,1552,3275,6184,2752,9108,3932,1909,5232,2702,3743,1181,7464,1925,4419,8051,796,893,1317,4384,8060,4508,4579,5755,6765,1733,117,7343,2719,154,5986,5197,2767,7902,2574,606,2351,558,2739,5230,310,3186,9391,6219,8236,6141,668,9697,1218,4273,8812,3986,2631,6865,6216,9427,3287,5480,1000,8315,3384,4275,630,9182,8713,9918,3415,3572,9152,6451,8058,9499,1922,1988,1525,3348,6806,6996,9026,7077,6816,6489,3395,3714,3595,1134,7325,3761,4924,1157,4308,9439,2307,9943,821,4355,5258,5927,9518,6464,3397,942,8028,3266,639,62,2752,5404,2183,2678,8969,7628,6666,8509,1246,5546,6889,6537,3432,47,4987,7518,1844,7433,2957,9424,8790,620,6029,7828,8353,5974,8560,4415,4788,1794,9941,7061,4465,5854,316,5598,7581,5248,1008,7063,1562,3062,1903,7599,3556,3807,7722,7223,1664,8909,4789,1482,9222,2706,1275,3133,5968,588,6682,8964,3264,2602,9032,559,7110,974,8997,9697,9367,2028,4764,3815,8957,8214,1710,5591,1100,4609,9684,9279,7118,256,5260,633,4223,5345,3597,5404,380,1414,5893,3404,8497,7643,7964,7377,5257,1343,5333,9756,8275,9046,3683,3874,6575,4983,1321,9673,8735,624,4445,3940,8732,620,3404,3246,6625,4801,3359,8994,7877,2082,1077,8220,8439,3208,362,3282,399,4196,104,2410,9877,9678,6326,1443,1647,8627,5171,9869,4092,9068,7882,5249,3254,8011,9659,7355,3520,6863,6891,2744,7413,6916,1100,3316,8290,4895,7062,6393,78,8002,3826,8206,1122,2555,2084,5833,6819,9490,6316,9488,8609,4711,3897,2446,7384,27,8203,137,5780,1161,9041,8716,3669,3225,1991,9653,7780,313,2234,3678,9120,1253,9659,3745,3469,5496,6550,8747,7934,5594,5987,5323,1277,6221,6939,9121,4829,331,3666,9932,5244,3512,704,4269,1726,2382,8691,7536,8362,7610,9446,1255,2997,7226,1821,1726,7208,6087,3478,5167,1880,4998,5870,9032,3941,7188,1880,8584,179,4042,239,3004,2414,4613,8279,6636,2603,9247,3039,7669,2180,7440,3274,5366,2395,2214,3257,4791,2081,1631,6292,4254,3733,9828,3644,3522,2550,4424,9989,7654,118,3505,216,5902,4131,2754,3333,4072,5624,4975,1160,3900,7783,1200,1361,9290,9284,1251,9817,6255,4832,8680,3667,8141,8951,1507,6395,4189,9869,7080,2084,5060,5153,5762,5680,7705,8415,2142,5837,6711,8460,3254,5306,869,2364,7737,3892,9618,605,2948,9414,371,4397,3807,1720,9327,961,3598,573,6542,8806,3522,2166,3899,9642,8781,1321,6424,7085,5827,3592,9206,8494,9878,8889,8246,3800,7856,4523,2859,7029,7764,7891,1825,2165,2544,9758,6080,6399,121,759,1222,5545,2181,9505,7805,6212,2743,3059,9952,2826,5660,4951,9826,6066,3340,2614,9186,8971,8866,832,319,4276,1441,5118,5409,2587,9550,2542,3995,4005,2197,6265,6070,9324,8711,9977,5444,296,8550,3154,5899,3510,1093,6249,8534,4619,1096,3509,5261,6209,1289,8425,3941,4955,3570,5466],
   
2. k = 165

复制代码

输出：34818
预期结果：33871

zltzlt

_2_ 发表于 2020-1-5 16:36
这能这么用吗？

我说的是缩进没错，并不是代码没错。

Unicorn#

zltzlt 发表于 2020-1-5 16:06
解答错误

输入：[13,999,1,2,3,9,11], k = 2

1. def solve(pages, k):
   
2.     if len(pages) <= 1 or k == 1:
   
3.         return sum(pages)
   
4.     else:
   
5.         return min(max(solve(pages[:i], j),solve(pages[i:], k-j))
   
6.                    for j in range(1, k) for i in range(len(pages)))

复制代码

zltzlt

Unicorn# 发表于 2020-1-5 16:41

输入以下数据超时：

1. pages = [393,8306,2935,9673,3769,9181,4804,199,5305,9089,3522,9676,6083,5340,3634,55,2298,497,4892,977,5026,3253,8548,60,4016,6299,6812,7005,7047,6647,1961,8846,2064,8800,4873,1515,5526,1771,8045,1906,2015,8154,1107,4042,1549,9553,7278,2290,2378,3884,6901,6337,9797,5583,1435,2064,757,2313,4825,2102,5160,3916,4558,7694,2851,7149,8104,9531,2943,3490,5390,6865,122,2511,3567,7822,897,9675,7369,6949,1923,6926,7869,2205,961,2313,9166,5848,1568,8898,4921,9982,9025,529,1235,405,8847,3816,156,2416],
   
2. k = 10001

复制代码

TJBEST

版主，我的写好了，您测试一下吧 不过看到您测试的 1000本书165个人 我感觉肯定超时了

阴阳神万物主

唉~从给出的示例来看找不到规律……我再编编别的数据。
从给出的示例猜测是平均数以上最小的那个分钟，没有就向上取整。
但是猜测应该不对。
话说 k 的取值范围是 0<k<=len(pages) 对吧？话说描述中又出现了 先是复数形式后来一般形式 的情况呢。

zltzlt

阴阳神万物主 发表于 2020-1-5 17:35
唉~从给出的示例来看找不到规律……我再编编别的数据。
从给出的示例猜测是平均数以上最小的那个分钟，没 ...

k 可能超过 len(pages)。

TJBEST

Croper 发表于 2020-1-5 15:45
...好吧，思路方向错了。。。
重新写了个动态规划的。。总感觉会很慢啊。。。

问一下，内部函数调用page不应该加nolocal吗？内部函数没有page的声明啊，难道外部参数具有特性？
初学，望勿喷

Croper

恩。。怎么说呢。。
我说说我的理解把

这就是所谓的"python的变量都是标签"，
而使用赋值符号'='其实是把标签贴到另外一个实体上去，而其他大部分操作都是直接操作标签指向的实体。

当我没有加nonlocal的时候，函数内部和外部的“page"其实是两个标签，但他们指向同一实体。
我在函数内部并没有使用”=“重新贴标签，操作的都是标签共同指向的实体，因此加不加nonlocal无所谓。

而当加了nonlocal的时候，就表明函数内部和外部的同名变量是同一个标签，这个时候”=“重新赋值就会影响外部的量。

Croper

改良版来喽，代码长了不少
实测要快一倍左右，主要是递归的时候会先确定一个八九不离十估计值，然后在估计值左右查找，要快得多：

1. def func_3003(page,n):
   
2.     """
   
3.     300期留名
   
4.     """
   
5.     t=[0]
   
6.     for i in page:
   
7.         t.append(t[-1]+i)
   
8.     buffer={}
   
9.     def dp(k,n):
   
10.         if (k,n) in buffer:
    
11.             return buffer[(k,n)]
    
12.         i=1
    
13.         ret=t[k]
    
14.         if (n>1):
    
15.             a=ret/n*(n-1)
    
16.             p,q=0,k
    
17.             while (p<q):
    
18.                 r=(p+q)//2
    
19.                 if (t[r]<a):
    
20.                     p=r+1
    
21.                 else:
    
22.                     q=r
    
23.             
    
24.             a,b=dp(p,n-1),t[k]-t[p]
    
25.             if (a==b):
    
26.                 ret=a
    
27.             elif (a<b):
    
28.                 while (a<b):
    
29.                     a0,b0=a,b
    
30.                     p+=1
    
31.                     a,b=dp(p,n-1),t[k]-t[p]
    
32.                 ret=min(max(a,b),max(a0,b0))
    
33.             elif (a>b):
    
34.                 while (a>b):
    
35.                     a0,b0=a,b
    
36.                     p-=1
    
37.                     a,b=dp(p,n-1),t[k]-t[p]
    
38.                 ret=min(max(a,b),max(a0,b0))
    
39. 
    
40.         buffer[(k,n)]=ret
    
41.         return ret
    
42. 
    
43.     return dp(len(page),n)

复制代码

zltzlt

Croper 发表于 2020-1-5 20:28
改良版来喽，代码长了不少
实测要快一倍左右，主要是递归的时候会先确定一个八九不离十估计值，然后在估计 ...

没有超时，但是超出内存限制。

zltzlt

Stubborn 发表于 2020-1-5 20:21

输入 pages = []，k = 1 出错。

ValueError: max() arg is an empty sequence

Croper

zltzlt 发表于 2020-1-5 20:32
输入 pages = []，k = 1 出错。

ValueError: max() arg is an empty sequence

不用测了。。他补上if之后比我快多了。。。。
我完全没有想到那里去。。

Stubborn

Croper 发表于 2020-1-5 20:36
不用测了。。他补上if之后比我快多了。。。。
我完全没有想到那里去。。

最多就补个 if not len(pages):retrun 0

Stubborn

zltzlt 发表于 2020-1-5 20:32
输入 pages = []，k = 1 出错。

ValueError: max() arg is an empty sequence

我补个 if not len(pages):retrun 0