我的算法题——蓝桥杯校选赛

注意!:之前算法太菜了考虑不周,后面有时间更改


问题描述   小明开了一家花店,这天,有个客户定了非常多的花,按客户的需要,这些花要排成 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; 
}
经验分享 程序员 微信小程序 职场和发展