三星全球软考的一道题
题外话
目前三星软件相关的岗位通常需要进行软件考试，该考试有三个级别：advanced、professional、expert。不同的人员需要通过不同的级别。通常是应届生需要过advanced才能发给offer，社招需要过professional才能发offer，老员工没有过professional的也一直在奋斗着。该考试由swexpertacademy团队主持，该网站内网才能访问。通常每月都有两次professional考试，expert考试大概每季度一次，题目都是新出的，且都是保密的不容许传到公网。
一道professional考题
一道泄漏到公网的考题：https://zhidao.baidu.com/question/941727649766572692.html
这个题目是2017年的professional考题。大概意思是，在一个岛屿的周围分布着大小不一的石油资源，几家公司来参与开采石油，资源分配的一个问题。
如图所示，在岛屿周围有四个石油资源分布，大小为6，13，10，2。然后有两家公司参与石油开采，为了石油资源分配的公平，要使他们各自分到的资源总量尽可能差别小，而且为了便于他们的开采作业，一个公司的资源应该是在岛周围连起来的几个或者仅此一个。这个例子中，应该把13分给一个公司，剩下的分为另一个。这样两家公司的资源差别是5，且满足差别最小、各公司的资源连在一起的要求。
如果资源分布是6，13，2，10。那么这个最小的值是1，因为13和2分一块，剩下的分为另一块。
一些参数的范围
- 参与开采的公司数目N不小于2，且不大于25
- 石油资源数M不小于N，且不大于50
- 每个石油资源的大小为整数，不小于1，且不大于100000
- 每一个石油资源都需要分配给开采公司，且只能分配给一个开采公司
- 一个开采公司的石油资源必须连接在一块
5个测试样例
（每两行为一个测试样例，其中第一行为公司数N和石油资源数M、第二行为石油资源的大小沿顺时针的分布）
2 4
6 13 10 2
2 4
6 13 2 10
4 9
100 92 133 201 34 34 34 94 108
6 16
32 42 9 27 31 18 9 2 47 36 43 33 29 32 32 48
10 25
25875 24373 20160 11834 28071 7488 28298 7519 8178 17774 32271 1764 2669 17193 13986 3103 8481 29214 7628 4803 4100 30528 2626 1544 1925
输出分配后，获得资源最多的一个公司与资源最少的一个公司二者的石油资源差值。
格式#T 结果，其中T为样例编号。
#1 5
#2 1
#3 29
#4 24
#5 18390
解法
待续。。。
Welcome to donate
