首页 > 代码库 > bjfu1097 图标排列
bjfu1097 图标排列
这是2011年百度之星的一道题。这题的做法就是找规律，规律找对了，代码极水。规律我一开始也没有找到，后来经人提醒，发现如下规律：对于每个开发者，其所有应用的分离度和一定是其第一个应用与最后一个应用的距离
例如对于15 8 5 2这组数据，有很多种排法，其中三种排法如下
1 2 3 1 2 3 1 2 1 2 1 2 1 1 1
0 0 0 3 3 3 3 3 2 2 2 2 2 1 1
这种排法，三个应用的分离度和分别为14，10，3，总和为27
1 1 1 1 2 2 3 2 3 2 2 1 1 1 1
0 1 1 1 0 1 0 2 2 2 1 8 1 1 1
这种排法，三个应用的分离度和分别为14，6，2，总和为22
1 2 3 1 1 1 1 1 1 2 2 2 3 2 1
0 0 0 3 1 1 1 1 1 8 1 1 10 2 6
这种排法，三个应用的分离度和分别为14，12，10，总和为36
不难看出上述规律的正确性。
有了这个规律，要让所有图标的分离度和最大也就是让每个开发者的分离度和的和最大。不难想到，如果某开发者只有一个应用，那么其分离度和必为零，否则（也就是应用数大于等于2），要使该开发者的应用的分离度和最大也就是使其第一个应用与最后一个应用距离最大。这样一样，对于所有应用数大于等于2的开发者，其地位是完全相同的，于是，只需要依次从这些开发者里每次取出两个应用分别置于所有图标的两端即可。计算就很简单了，我的代码如下，其实还可以整理出更简洁的公式的：
/* * Author : ben */#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>#include <stack>#include <string>#include <vector>#include <deque>#include <list>#include <functional>#include <numeric>#include <cctype>using namespace std;#ifdef ON_LOCAL_DEBUG#else#endiftypedef long long LL;int main() {#ifdef ON_LOCAL_DEBUG freopen("data.in", "r", stdin);#endif int m, n, d, a; while (scanf("%d%d", &n, &m) == 2) { a = n - 1; LL ans = 0; for (int i = 0; i < m; i++) { scanf("%d", &d); if (d >= 2) { ans += a; a -= 2; } } printf("%I64d\n", ans); } return 0;}
bjfu1097 图标排列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。