基础算法 01

基础算法 01_贪心

有

每堆上有若干张，但纸牌总数必为

可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如

移动

从第三堆取四张牌放入第四堆，各堆纸牌数量变为:

从第三堆取三张牌放入第二堆，各堆纸牌数量变为:

从第二堆取一张牌放入第一堆，各堆纸牌数量变为:

输入格式

第一行包含整数

第二行包含

输出格式

输出使得所有堆的纸牌数量都相等所需的最少移动次数。

数据范围

输入样例：
4
9 8 17 6
输出样例：
3

分析：

这是一个展开的传递题，最左面的只能向最右边的传递，最右边的只能向最左面传递，而其他堆可以向两侧传递。显然，相邻的两堆纸牌传递两次及以上，是浪费的行为。所以，我们保证相邻两堆纸牌之间只会传递一次，要么左边传递给右边，要么右边传递给左端，而这个过程只会进行n-1次就可以让每堆纸牌数量达到平均值。

假定我们从左向右传递，a[i]与a[i + 1]之间进行传递，如果a[i]大于平均值，将a[i]多的部分分给a[i+1]，如果a[i]小于平均值，就让a[i+1]分给a[i]。到了最后一堆的时候，一定达到了平均情况。

我们发现，i影响的是i的下一堆，我们主是将下一堆的数量标记好就可以了，产生影响的时候，计数，这是产生了传递的次数。

代码：

 1 #include <cstdio>
 2 
 3 using namespace std;
 4 
 5 const int N = 110;
 6 
 7 int n;
 8 int a[N];
 9 
10 int main()
11 {
12     scanf("%d", &n);
13     int ave;
14     for (int i = 1; i <= n; i ++ )
15     {
16         scanf("%d", &a[i]);
17         ave += a[i];
18     }
19     
20     ave /= n;
21     
22     for (int i = 1; i <= n; i ++ )
23     {
24         a[i] -= ave;
25     }
26     
27     int ans = 0;
28     for (int i = 1; i < n; i ++ )
29     {
30         if (a[i] != 0) a[i + 1] += a[i], ans ++;
31     }
32     
33     printf("%d
", ans);
34     
35     return 0;
36 }

View Code

122. 糖果传递

题目：

有

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为

求使所有人获得均等糖果的最小代价。

输入格式

第一行输入一个正整数

接下来

输出格式

输出一个整数，表示最小代价。

数据范围

输入样例：
4
1
2
5
4
输出样例：
4

分析：

设x为前一个小朋有需要向后一个小朋友传递的糖果数，下面我们将题目进行转化

【我也搞不清要不要裂开，似乎是需要裂开的，这样才能像仓库选址，因为仓库选址本身就是在一条直线上的】在众多x中，因为他们自己的糖果数不同，所以他们相互传递的糖果数也不同，所以会出现x是正数、负数、和0.我们找到一个位置，这里的a的右边是负数，左边是正数或0。可以将这个点拆开，变成一条链。这个点表示，需要向左边分配0个或多个糖果，也也要向右边分配糖果。
再结合前面我们转化的关系，这样我们会发现，我们要让`|xn - S1|, |xn - S2|, |xn - s3|, ...., |xn - Sn|`最小，这就是需要先排个序，然后在中间位置坐标的点选择建立仓库，然后计算最短距离之和。就变成了仓库选址模型了。

这样就将问题转化为了仓库选址问题了。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 
10 const int N = 1000010;
11 
12 int n;
13 ll a[N];
14 ll s[N];
15 
16 int main()
17 {
18     scanf("%d", &n);
19     ll ave = 0;
20     for (int i = 1; i <= n; i ++ )
21     {
22         scanf("%lld", &a[i]);
23         ave += a[i];
24     }
25     ave /= n;
26     
27     for (int i = 1; i <= n; i ++ )
28     {
29         s[i] = s[i - 1] + ave - a[i];
30     }
31     
32     sort(s + 1, s + 1 + n);
33     // nth_element(s + 1, s + n / 2, s + n);
34     ll ans = 0;
35     for (int i = 1; i <= n; i ++ )
36         ans += abs(s[i] - s[(n + 1) / 2]);
37     printf("%lld
", ans);
38     
39     return 0;
40 }

View Code