本文共 1848 字，大约阅读时间需要 6 分钟。
1. 有N个人，其中一个明星和n-1个群众，群众都认识明星，明星不认识任何群众，群众和群众之间的认识关系不知道，现在如果你是机器人R2T2，你每次问一个人是否认识另外一个人的代价为0(1),试设计一种算法找出明星，并给出时间复杂度。
分析：这是一道老题，关键点在只有一个明星。首先分析一次询问的效果。is A 认识 B? (yes) A不是明星，B可能是明星 ；(no) A可能是明星，B是群众。所以一次询问可以删除一个人。总共有n个人，那么当然是O(n)啦。这类时间复杂度的问题一般都有一个O(1)的操作，看看这个操作有什么信息量，就可以很快确定了。
例如，如果一次询问可以知道他认识的人和不认识的人，那么就采用分治的方法了。时间复杂度就是O(log(n))，有这种场景的。
如果有2个明星呢？明星之间互不认识。那么还是O(n)，因为找到一个明星之后询问其他所有人，选出不认识的
如果x个呢？当然也是O(n)啦。同样的操作进行删除，最后可以找个一个明星，然后再询问其他人是否认识这个明星，选出不认识的
2. 有一个淘宝商户，在某城市有n个仓库，每个仓库的储货量不同，现在要通过货物运输，将每次仓库的储货量变成一致的，n个仓库之间的运输线路围城一个圈，即1->2->3->4->...->n->1->...，货物只能通过相邻的仓库之间运输，设计最小的运送成本（运货量*路程）达到淘宝商户的要求，并写出代码。
这个题目类似的题目有：有n个小朋友坐成一圈，每人有Ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1，求使所有人获得均等糖果的最小代价。设Xi为第i-1个小朋友分给第i个小朋友的糖果数，G为最后的平均数。其中X1为第n个小朋友分给第1个小朋友的糖果数。A1 +X1 + X2 = G
A2 + X2 - X3 = G
.
.
.
An + Xn - X1 = G
解得
X1 = X1
X2 = A1 - G - X1
X3 = A1 + A2 - G - G + X1
.
.
.
Xn = A(n-1)+A(n-2)+...A2+A1 - (n -1)* G + X1
则总开销为：|X1|+|X2|+...+|Xn| =|X1|+ |A1-G+X1| + |A2+A1-2*G+X1| + ... +|A(n-1)+A(n-2)+...A2+A1 - (n -1)* G + X1|
设s[i]=Ai+ ... +A1- i*G; 则上式=|X1| + ∑|s[i]+X1| ,1=< i<=n-1
设k为第一个分给第n个的数量为k，则k=-X1，上式为：|k| + ∑|s[i]-k| ,1=< i<=n-1
要使上式值最小，则k为0, s[1], s[2], ......s[n-1]的中位数。
原因：如果k的取值向左移动一个，则所有大于k的|s[i]-k|值加1，小于k的|s[i]-k|值便减1，k的取值向右移动一个同理。因此k的值为中位数时最小。
1 #include2 #include 3 #include 4 using namespace std; 5 const long long N = 2001000; 6 long long a[N], s[N], tar[N], n; 7 int main () 8 { 9 scanf ("%d", &n);10 for (long long i = 1; i <= n; i ++)11 scanf ("%d", &a[i]), s[i] = s[i - 1] + a[i];12 long long g = s[n] / n;13 for (long long i = 1; i < n; i ++)14 tar[i] = i * g - s[i];15 sort (tar + 1, tar + 1 + n);16 long long x = n >> 1, z = abs(tar[x]);17 for (long long i = 1; i <= n; i ++)18 z += abs (tar[i] - tar[x]);19 printf ("%lld\n", z);20 return 0;21 }
转载地址：http://pkrvi.baihongyu.com/