贪心算法2（c++）

最大子矩阵
描述
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1*1)子矩阵。
比如，如下4*4的矩阵

0- 2 -7 0

9 2 -6 2
-4 1 -4 1

-1 8 0-2

的最大子矩阵是
9 2
-4 1
-18
这个子矩阵的大小是15。

输入输入是一个N*N的矩阵。输入的第一行给出N(0<N<=100)。再后面的若干行中，依次(首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数…)给出矩阵中的N2个整数，整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[-127,127]。
输出
输出最大子矩阵的大小。
样例输入
4

0 -2 -7 0

9 2 -6 2

-4 1 -4 1

-1 8 0 -2
样例输出
15

#include <iostream>
using namespace std;
int main()
{int n;cin>>n;int a[110][110] = {0};int b[110][110] = {0};for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){cin>>a[i][j];if(i==1){b[i][j] = b[i][j-1]+a[i][j];}else{b[i][j] = b[i-1][j]+a[i][j]+b[i][j-1]-b[i-1][j-1];}}}int cnt = 0;int ma = -99999;for(int i1 = 1;i1<=n-1;i1++){for(int j1 = 1;j1<=n-1;j1++){for(int i2 = i1+1;i2<=n;i2++){for(int j2 = j1+1;j2<=n;j2++){if(i1==1&&j1==1){cnt = b[i2][j2];}else if(i1!=1&&j1==1){cnt = b[i2][j2]-b[i1-1][j2];}else if(i1==1&&j1!=1){cnt = b[i2][j2]-b[i2][j1-1];}else if(i1!=1&&j1!=1){cnt = b[i2][j2]-b[i2][j1-1]-b[i2][j1-1]+b[i1-1][j1-1];}ma = max(cnt,ma);}}}}cout<<ma;return 0;
}

均分纸牌
题目描述
有n堆纸牌(2<n≤200)，排成一行，编号分别为1,2....n。已知每堆纸牌有一定的张数，且张数之和均为n的倍数。移动各堆中的任意张纸牌，使每堆的数量达到相同，且移动次数最少。
移动规则:每次可以移动任意的张数，第1堆可以移向第2堆第2堆可以移向第1堆或第3堆，。第n堆只可以移向第n-1堆。

例如，当n=4时:

堆号1 2 3 4

张数3 5 4 8
移动的方法有许多种，其中的一种方案:

① 第2堆向第1堆移动2张，成为:5 3 4 8

②第4堆向第3堆移动3张，成为:5 3 7 5

③第3堆向第2堆移动2张，成为:5 5 5 5

经过三次移动，每堆都成为5张。
输入
第一行一个整数n。
第二行n个整数，用空格分隔。
输出
1个整数(表示最少移动次数)

样例

输入复制
4
3 5 4 8
输出复制
2

#include <iostream>
using namespace std;
int main()
{int n;cin>>n;int a[210] = {0};int sum = 0;for(int i = 0;i<n;i++){cin>>a[i];sum = sum+a[i];}sum = sum/n;int cnt = 0;for(int i = 0;i<n;i++){if(a[i]<sum){a[i+1] = a[i+1]-(sum-a[i]);a[i] = sum;cnt++;}else if(a[i]>sum){a[i+1] = a[i+1]+a[i]-sum;a[i] = sum;cnt++;}}cout<<cnt;return 0;
}