cf 1084A The Fair Nut and Elevator 暴力枚举

缘起

继续和电梯死磕~ cf 1084A The Fair Nut and Elevator

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
有一个电梯，它初始时会停留在第k层楼，每当有一个人要从第a楼去第b楼，电梯就会始终按照 
k->a->b->k的路线去运行，而且电梯最多只会同时容纳一个人，现在有一个n层楼的楼房，第i层有ai个人，
这一层的每个人每天都要按照i->1->i的顺序使用电梯，问将电梯的k设为多少时，每天的运行距离最少。

【输入】
第一行是n（1≤n≤100）, 表示楼层的数量
然后第二行是n个数字. a1,a2,…,an (0≤ai≤100) ,表示第i层人的数量

【输出】
输出答案

【样例输入】
3
0 2 1

【样例输出】
16

【限制】
1s

n太小了. 所以暴力枚举k, 而对每个k, 计算耗时O(n), 所以复杂度是O(n^2). 此题甚水~ 电梯甚笨~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL
#define ABS(a,b) ((a)>(b)?((a)-(b)):((b)-(a)))
int n,a[105];

int kk(int i, int j) // 第j层的一个人 j->1->j 的使用电梯(电梯设定为i)
{
	return (ABS(i,j)+ABS(j,1)+ABS(1,i))<<1; // i->j->1->i
}

int cal(int i) // 设定为i
{
	int ans = 0;
	for (int j = 1; j<=n;j++) // 考虑第j层的aj个人
	{
		ans+=a[j]*kk(i,j);
	}
	return ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 1; i<=n; i++)
	{
		scanf("%d", a+i);
	}
	int ans = 0x3f3f3f3f, k;
	for (int i = 1,x;i<=n;i++)
	{
		x = cal(i);
		if (ans>x)
		{
			ans = x;
			k = i;
		}
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

Status Accepted
Time 31ms
Memory 8kB
Length 689
Lang Microsoft Visual C++ 2010
Submitted 2019-09-11 11:22:23
Shared
RemoteRunId 60372325