娱乐 每 日 算 法 挑 战 【第3期·周末特辑】

[Mr.K 018]

本期是周末特辑，是今明两天的题目哦！

今天的题目是BIT2018年校赛的A题。不出意外的话，下周的周末特辑会是B题，再下周C题，一直出到J题√

据说那年A题是个签到题，不过毕竟是第一周嘛，就白给一下啦。下面看题：

A 克鲁苏的呼唤（搬运工注：原文如此）

克苏鲁的眷族之一，隐藏在数字中的邪神，正在从宇宙深渊中复苏。

在他潜移默化的引导下，人类建立了自以为傲的计算机系统，而这，正是他复苏的物质基石。

是否经常因为代码而陷入疯狂？

下降的san值（sanity，理智、精神正常）正是受到邪神启蒙的证明。

现在共有N种算法，学习算法i将会导致san值下降

初始san值是S，最多可以学习多少个算法还能保持san值大于0？

 

输入

多组用例，以文件尾EOF结束输入，每组用例第一行两个整数N和S分别代表算法的数量和初始san值，第二行N个整数，第i个数代表学习算法i降掉的san值

 

 

输出

对于每组用例输出一个整数占一行，表示保持san值大于0的情况下，最多能学的算法数量

 

样例输入

1 1
1
5 10
1 2 3 4 5

 

样例输出

0
3

 

样例解释

对于第一组用例，学习算法1会使得san值变成0，故无法学习任何算法；

对于第二组用例，学习任意四个算法都会使得san值变成0，而学习算法1,2,3是可以的。

四月 11, 2020，由Mr.K 018修改

[yhz012]

艹今天居然是隐藏在数字中的邪神（x

 

艹难怪写代码写久了我觉得san值下降

太艹了（

 

艹是01背包？不过每个算法的价值都是1的话，那直接升序从小的开始拿就好了吧……

或者直接求最小S个元素，用快排的分割部分就好，然后拿这最小S个sort一遍就好了

 

或者更精确地可以先扫一遍，拿到最小值min_i san，然后求最小(S / min)个元素

当然如果X比(S / min)小的话那就直接sort就好了

 

当然我这里是假定第二行全都是正整数的，也就是不存在没有代价就能学会的算法！（逃

 

 

四月 11, 2020，由yhz012修改

[Mr.K 018]

我觉得我san值也在下降，召唤阵这么重要的东西怎么能连续忘记两次呢

下面是召唤阵：

引用

INVOKE @ZERC

INVOKE @inuisanaa

INVOKE @随性而为

INVOKE @NianRuoshui

INVOKE  @摸鱼奇才咖啡喵

INVOKE @fubuki.ss

RET

 

[NianRuoshui]

艹是克苏鲁 怪不得写代码感觉在掉san

感觉sort排个序然后依次减好像就行了

[随性而为]

我感觉该说的前面两位都说了，我也想不出什么骚话，此贴完结所以为了别让邪神复活应该呼吁全世界砸了计算机

话说楼主召唤阵不顶用啊，通知都没一声

四月 11, 2020，由随性而为修改

[ZERC]

2 小时前, 随性而为 说道:

我感觉该说的前面两位都说了，我也想不出什么骚话，此贴完结所以为了别让邪神复活应该呼吁全世界砸了计算机

话说楼主召唤阵不顶用啊，通知都没一声

的确，真的没有通知....

[Mr.K 018]

1 小时前, ZERC 说道:

的确，真的没有通知....

这一定是论坛的问题，不是我的问题

绝对是这样的

[ZERC]

1 小时前, Mr.K 018 说道:

这一定是论坛的问题，不是我的问题

绝对是这样的

原来是这样啊www

看来引用召唤不可靠www

还是要自己一个一个打出来www

[Mr.K 018]

刚刚, ZERC 说道:

原来是这样啊www

看来引用召唤不可靠www

还是要自己一个一个打出来www

我是自己一个一个打的啊

鼠标放上去还能看到个人信息呢

[ZERC]

1 分钟前, Mr.K 018 说道:

我是自己一个一个打的啊

鼠标放上去还能看到个人信息呢

默哀....

@Mr.K 018 

看来真的是论坛bug

就是不知道如何复现....

四月 11, 2020，由ZERC修改

[Mr.K 018]

引用

@ZERC

试试这样？

[ZERC]

8 分钟前, Mr.K 018 说道:

试试这样？

这个我收到了一个通知。

我去其他贴召唤你试试

更新：收到了吗？

更新2：你这引用是用F12做的吗？感觉原因可能是这个

四月 11, 2020，由ZERC修改

[可洛]

Matlab的写法比较熟悉，就假设用matlab吧（虽然matlab算是伪代码吧）

手头没有Matlab没法测试，写出bug不管啊（甩

而且很久没写了，你们谁有matlab可以去跑跑看www

代码以下：

剧透

 

function My_Output = Sanity_Calc([N S], Array)

i = 0; % Set initial count to 0

Array2 = sort(Array);

while S>=0 && N > 0

S = S - Array2[1]  % Matlab has 1-based index

Array2[1] = [] % Remove min value

i = i + 1; % Increase count by 1

N = N - 1; % Decrease total count N by 1

end

if N > 0 

i = i - 1; % Remove extra count from last loop

end

 

其实，既然第二个input，也就是那个N个整数的array是1*N的，N这个input根本就不需要吧喂！

剩余的算法数量查Array2就知道了www

四月 11, 2020，由可洛修改

[Mr.K 018]

41 分钟前, 可洛 说道:

Matlab的写法比较熟悉，就假设用matlab吧（虽然matlab算是伪代码吧）

手头没有Matlab没法测试，写出bug不管啊（甩

而且很久没写了，你们谁有matlab可以去跑跑看www

代码以下：

  显示隐藏内容

 

function My_Output = Sanity_Calc([N S], Array)

i = 0; % Set initial count to 0

Array2 = sort(Array);

while S>=0 && N > 0

S = S - Array2[1]  % Matlab has 1-based index

Array2[1] = [] % Remove min value

i = i + 1; % Increase count by 1

N = N - 1; % Decrease total count N by 1

end

if N > 0 

i = i - 1; % Remove extra count from last loop

end

 

其实，既然第二个input，也就是那个N个整数的array是1*N的，N这个input根本就不需要吧喂！

剩余的算法数量查Array2就知道了www

暂时发不出糖了，可以等明天吗（悲

[ppzt]

一开始以为是背包问题 然后发现问的是最多学几个算法……

hmm……应该可以证明贪婪就是最优解？所以从最小的开始拿拿到不能拿就行了……