当前位置:   article > 正文

【2024东区信息学小学组】5.作业分配(assign)_【2024年中山市东区】作业分配(assign)

【2024年中山市东区】作业分配(assign)

描述

旅行归来的 Jimmy 又要面对新的作业了。这次一共有 N 份作业,Jimmy 估计每份作业需要 Ti 的时间完成。
由于 Jimmy 急着出去玩,因此他决定请 Chen 来跟他一起完成作业。Jimmy 可以把某些作业分给 Chen 来做,同时他自己就做剩下的作业。为了不抛下好朋友,Jimmy 和 Chen约定,如果他俩谁先完成了作业,那就要等另一个人也完成了作业,再一起去玩。
Jimmy 和 Chen 都想尽快出去玩,所以请你帮他们算一下,两人最少要花多少时间才能完成作业。

输入描述

第一行一个正整数 N ,表示一共有 N 份作业。
第二行 N 个正整数 T1, T2, · · · , TN ,表示完成每份作业需要的时间。

输出描述

一行一个整数,表示两人完成所有作业所需的最少时间。

用例输入 1 

5
8 3 7 2 5

用例输出 1 

13

用例输入 2 

2
1000 1

用例输出 2 

1000

用例输入 3 

9
3 14 15 9 26 5 35 89 79

用例输出 3 

138

提示

【样例 1 解释】

Jimmy 可以做第 1 份和第 5 份作业,花费 8 + 5 = 13 的时间;Chen 则要做第 2, 3, 4 份
作业,花费 3 + 7 + 2 = 12 的时间。因此两人要花 13 的时间来完成所有作业,这也是最少的用时。

【测试点约束】

对于 30% 的数据,满足 1 ≤ N ≤ 20。
对于 100% 的数据,满足 1 ≤ N ≤ 100,1 ≤ Ti ≤ 1000。

水水水!!思路特简单,01背包问题,容量就是总和除以二,重量就是完成每一份作业的时间,价值就是重量,最后输出总和减去容量就行了。

代码:

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int a[100001],f[1000001];
  4. int main()
  5. {
  6. int n,ans=0;
  7. scanf("%d",&n);
  8. for(int i=1;i<=n;i++)
  9. {
  10. scanf("%d",&a[i]);
  11. ans+=a[i];
  12. }
  13. int sum=(ans+1)/2;
  14. for(int i=1;i<=n;i++)
  15. {
  16. for(int j=sum;j>=a[i];j--)
  17. {
  18. f[j]=max(f[j],f[j-a[i]]+a[i]);
  19. }
  20. }
  21. printf("%d",ans-f[sum]));
  22. return 0;
  23. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小蓝xlanll/article/detail/718308
推荐阅读
相关标签
  

闽ICP备14008679号