我的算法题——蓝桥杯校选赛
注意!:之前算法太菜了考虑不周,后面有时间更改
问题描述 小明开了一家花店,这天,有个客户定了非常多的花,按客户的需要,这些花要排成 n 行 m 列。 小明要将这些花运送到客户那,然而由于花太多,需要分两辆车才能装下。 小明怕自己弄错花的顺序,因此在分车的时候,他准备将前面一些列(注意不是行)的花放在第一辆车上,将其余的花放在第二辆车上。 已知每盆花的重量,要使第一辆车和第二辆车尽可能总重量一致,请帮助小明分装这些花,请告诉小明两辆车的重量最小差多少。输入格式 输入的第一行包含两个整数 n, m,分别表示行数和列数。 接下来 n 行,每行 m 个正整数,分别表示每盆花的重量。输出格式 输出一个整数,表示总重量最接近时两车的重量之差(的绝对值)。样例输入3 4 1 2 3 9 5 6 7 8 2 3 4 9样例输出7样例说明 将前 3 列放一辆车,后 1 列放一辆车,第一辆比第二辆重 7 。评测用例规模与约定 对于 30% 的评测用例,2 <= n, m <= 20。 对于 70% 的评测用例,2 <= n, m <= 100。 对于所有评测用例,2 <= n, m <= 1000,每盆花的重量不超过 1000。 思路: 已知是n行m列,可先将每列总花盆数存入数组中得到大小为m的数组。就样例为 8 11 14 26.再比较第一位与最后一位的差值,若小于0则将前标往后挪,加上第二位的值再比较是否小于0,若大于0则往前挪减去前一位值。就例题而言:8-26=-18<0,-18+11=-7<0,-7+14=7,则最小绝对值为7.以下是我的代码:
#include <iostream>
#include <math.h>
using namespace std;
int main(){
cout<<"请输入两个整数代表行列数:";
int n,m;
cin>>n>>m;
int a[n][m];
cout<<"接下来输入每行每盆花的重量" <<endl;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
int b[m];
for(int i=0;i<m;i++)
b[i]=0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
b[i]+=a[j][i];
int high=m-1,low=0,counts;
counts=b[low]-b[high];
while(high-1!=low){
if(counts<0)
{
low++;
counts+=b[low];
}
else
{
high--;
counts-=b[high];
}
}
cout<<"最小差为:"<<abs(counts)<<endl;
}
