这是百度之星在2011的初赛的一道题目，其实没啥难度，关键是找对方法。。
题目：
图标排列描述百度应用平台上有很多有趣的应用，每个应用都由一个开发者开发，每个开发者可能开发一个或多个应用。百度的工程师们想把应用尽可能好的推荐给用户。研究发现，同一个开发者开发的程序的图标有很大的相似性。如果把同一个开发者开发的应用放在一起，用户很快就会厌倦相似的图标，如果把这些图标穿插摆放效果就会好很多。现在工程师想给用户推荐来自m个开发者的n个应用，在推荐的时候这些应用的图标将排成整齐的一行展示给用户，相邻两个图标之间的距离正好是1，工程师们想让这些图标尽可能的穿插摆放。为了衡量穿插摆放的效果，给每个图标定义一个“分离度”，分离度的值是指当前图标和它左边最近的来自同一个开发者的图标之间的距离。如果一个图标左边没有来自同一个开发者的图标，则分离度为0。所有图标穿插摆放效果的值定义为所有图标的分离度之和。已知每个开发者开发的应用个数，请帮助百度的工程师找到图标穿插摆放效果的最大值。 输入输入的第一行包含两个整数n和m，用一个空格分隔，分别表示应用的个数和开发者的个数。第二行包含m个正整数，相邻两个数之间用一个空格分隔，表示每个开发者开发的应用个数，这些整数之和必然等于n。 输出输出一个整数，表示图标穿插摆放效果的最大值。 样例输入8 33 3 2 样例输出15提示对于20%的数据，n≤ 10；对于40%的数据，n≤ 100。对于100%的数据，1≤ m ≤ n ≤ 100,000
1：问题可以简化为求一个应用数最左端的数和最右端的距离。用贪心算法解决，即每次最优排列当前最少开发者应用个数的图标。 示例： 8 3 3 3 2 先安排2个应用的开发者： 3 0 0 0 0 0 0 3 安排3个应用开发者： 3 2 0 0 0 0 2 3 期中一个应用先不安排 最后填入安排后的任意空格均可 安排3个应用开发者： 3 2 1 0 0 1 2 3 最后任意安排剩下的 3 2 1 1 2 1 2 3 如图：
代码很简单 从略。。。。。。
本文出自 “沧海龙腾” 博客，请务必保留此出处http://canghailongteng.blog.51cto.com/4967747/877951
![[译]技术公司十年经验的职场生涯回顾](https://img8.php1.cn/3cdc5/24912/711/b6574f3292f9dc00.png)
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 