LeetCode 58 区间和 44开发商购买土地

58 区间和

#include <iostream>

C++ 标准库里的输入输出流头文件，用了它之后才能使用这些最常见的输入输出工具：

cout        输出

cin        输入

endl        换行并刷新缓冲区

#include <vector>

C++ 标准库中动态数组容器vector 的头文件。

using namespace std;

把 std 命名空间里的所有名字，引入到当前作用域，最好在后缀为.cpp文件中使用，不可以在头文件中使用。

面对大量数据，读取/输出操作使用scanf("%d", &vec[i]);/printf("%d\\n", sum);

方法一，暴力方法：

#include<iostream>
#include<vector>
using namespance std;

int main(){
int n,a,b;
cin>>n;
vector<int> nums(n,0);
for(int i=0;i<n;i++){
cin>>nums[i];
}
while(cin>>a>>b){
int sum=0;
for(int j=a;j<=b;j++){
sum=sum+nums[j];
}
cout<<sum<<endl;
}
}

运行失败，分析原因：

1，using namespance std;拼写错误，修改为using namespace std;

修改后如下，运行成功：

#include<iostream>
#include<vector>
using namespace std;

int main(){
int n,a,b;
cin>>n;
vector<int> nums(n,0);
for(int i=0;i<n;i++){
cin>>nums[i];
}
while(cin>>a>>b){
int sum=0;
for(int j=a;j<=b;j++){
sum=sum+nums[j];
}
cout<<sum<<endl;
}
}

方法二，前缀和，先计算前i个数组的和，之后通过作差得出结果：

#include<iostream>
#include<vector>
using namespace std;

int main(){
int n,a,b;
cin>>n;
vector<int> nums(n,0);
vector<int> p(n,0);
int sum=0;
for(int i=0;i<n;i++){
cin>>nums[i];
sum = sum+nums[i];
p[i]=sum;
}
while(cin>>a>>b){
if(a==0)
cout<<p[b]<<endl;
else
sum=p[b]-p[a-1];
cout<<sum<<endl;
}
}

运行结果不符合预期，分析原因如下：

else下有两行代码，忘记加大括号括起来，修改后如下，运行成功：

#include<iostream>
#include<vector>
using namespace std;

int main(){
int n,a,b;
cin>>n;
vector<int> nums(n,0);
vector<int> p(n,0);
int temp=0;
for(int i=0;i<n;i++){
cin>>nums[i];
temp = temp+nums[i];
p[i]=temp;
}
while(cin>>a>>b){
int sum=0;
if(a==0)
cout<<p[b]<<endl;
else{
sum=p[b]-p[a-1];
cout<<sum<<endl;
}
}
}

44 开发商购买土地

#include <climits>

C++ 标准库头文件，里面定义了各种整数类型的最小值 / 最大值:

前缀和，先做累加，计算前i个数组的和，之后通过作差得出结果，这里是二维数组，需要考虑横向和纵向，横向前i个数组的和，纵向前j个数组的和。

计算某一行或某一列的和，只需要固定行或者列：

#include<iostream>
#include<vector>
#include<climits>
using namespace std;
int main(){
cin<<n<<m;
vector<vector<int>> nums(n,vector<int>(m,0));
int sum=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin<<nums[i][j]; //输入每个区块的权值
sum+=nums[i][j]; //计算总权值
}
}
vector<int> h(n,0);
for(i=0;i<n;i++){
for(int j=0;j<m;j++){
h[i]+=nums[i][j]; //计算每行之和
}
}
vector<int> z(m,0);
for(i=0;i<n;i++){
for(int j=0;j<m;j++){
z[j]+=nums[i][j]; //计算每列之和
}
}
int result = INT_MAX;
for(int cuth=0;cuth<n;cuth++){
result=min(result,sum-h[cut]); //按横向划分
}
for(int cutz=0;cutz<m;cutz++){
result=min(result,sum-z[cut]); //按纵向划分
}
cout>>result>>endl;
}

运行报错，分析错误如下：

1，输入输出符号写反了；

2,变量声明漏了几个；

3,几个变量名不一致。

修改后如下，运行成功，但是输出不符合预期：

#include<iostream>
#include<vector>
#include<climits>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>> nums(n,vector<int>(m,0));
int sum=0;
int i,j;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
cin>>nums[i][j]; //输入每个区块的权值
sum+=nums[i][j]; //计算总权值
}
}
vector<int> h(n,0);
for(i=0;i<n;i++){
for(j=0;j<m;j++){
h[i]+=nums[i][j]; //计算每行之和
}
}
vector<int> z(m,0);
for(i=0;i<n;i++){
for(j=0;j<m;j++){
z[j]+=nums[i][j]; //计算每列之和
}
}
int result = INT_MAX;
for(int cuth=0;cuth<n;cuth++){
result=min(result,sum-h[cuth]); //按横向划分
}
for(int cutz=0;cutz<m;cutz++){
result=min(result,sum-z[cutz]); //按纵向划分
}
cout<<result<<endl;
}

分析如下：

1，计算每列之和中，i和j反了；

2，前面是计算了每列或每行之和，没有计算前i个数组的和或前j个数组的和；

3，这道题虽然也是前缀和，但是和之前的58那道题计算区间和不同的是，这道题是要求两边差的绝对值最小。

修改后的代码如下，成功运行并输出预取结果：

#include<iostream>
#include<vector>
#include<climits>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>> nums(n,vector<int>(m,0));
int sum=0;
int i,j;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
cin>>nums[i][j]; //输入每个区块的权值
sum+=nums[i][j]; //计算总权值
}
}
vector<int> h(n,0);
for(i=0;i<n;i++){
for(j=0;j<m;j++){
h[i]+=nums[i][j]; //计算每行之和
}
}
vector<int> z(m,0);
for(j=0;j<m;j++){
for(i=0;i<n;i++){
z[j]+=nums[i][j]; //计算每列之和
}
}
int result = INT_MAX;
int hr=0,zl=0;
for(int cuth=0;cuth<n;cuth++){
hr+=h[cuth];
result=min(result,abs(hr-(sum-hr))); //按横向划分
}
for(int cutz=0;cutz<m;cutz++){
zl=zl+z[cutz];
result=min(result,abs(zl-(sum-zl))); //按纵向划分
}
cout<<result<<endl;
}