2011年百度之星程序大赛初赛第一场题目(图标排列)

第一题:图标排列

百度应用平台上有很多有趣的应用,每个应用都由一个开发者开发,每个开发者可能开发一个或多个应用。百度的工程师们想把应用尽可能好的推荐给用户。
研究发现,同一个开发者开发的程序的图标有很大的相似性。如果把同一个开发者开发的应用放在一起,用户很快就会厌倦相似的图标,如果把这些图标穿插摆放效果就会好很多。
现在工程师想给用户推荐来自m个开发者的n个应用,在推荐的时候这些应用的图标将排成整齐的一行展示给用户,相邻两个图标之间的距离正好是1,工程 师们想让这些图标尽可能的穿插摆放。为了衡量穿插摆放的效果,给每个图标定义一个“分离度”,分离度的值是指当前图标和它左边最近的来自同一个开发者的图 标之间的距离。如果一个图标左边没有来自同一个开发者的图标,则分离度为0。所有图标穿插摆放效果的值定义为所有图标的分离度之和。
已知每个开发者开发的应用个数,请帮助百度的工程师找到图标穿插摆放效果的最大值。

输入描述
输入的第一行包含两个整数n和m,用一个空格分隔,分别表示应用的个数和开发者的个数。
第二行包含m个正整数,相邻两个数之间用一个空格分隔,表示每个开发者开发的应用个数,这些整数之和必然等于n。

输出描述
输出一个整数,表示图标穿插摆放效果的最大值。

样例输入
8 3
3 3 2

样例输出
15

提示
对于20%的数据,n≤ 10;
对于40%的数据,n≤ 100。
对于100%的数据,1≤ m ≤ n ≤ 100,000

由于找不到数据测试的地方,且记录下我的代码吧,可能也有不对,欢迎路过的人批评指正

 

2011年百度之星程序大赛初赛第一场题目(图标排列)
 1 #include<iostream>
 2 #include<stdio.h>
 3 using namespace std;
 4 int main()
 5 {
 6     int n,m;
 7     while(scanf("%d%d",&n,&m)!=EOF)
 8     {
 9         int i,a,b=0;
10         for(i=1;i<=m;i++){
11             scanf("%d",&a);
12             if(a>1) b++;
13         }
14         printf("%d\n",b*(n-b));
15     }
16     return 0;
17 }
View Code

2011年百度之星程序大赛初赛第一场题目(图标排列)

上一篇:Linux shell 脚本攻略之生成任意大小的文件


下一篇:array-indexOf方法