关于计算两侧的"魔法对"的数量,
一开始我用的是很无脑的方案,两层 for 遍历,
代码: 全选
int count_pair1(vector<int> &arr, int begin, int end )
{
register int pair = 0;
register int L, R;
for (L = begin; L < end; L++)
for (R = L+1; R <= end; R++)
if ( arr[L] > arr[R] )
pair++;
return pair;
}
测试数据稍微增加就卡的不行,在优化的时候发现这段写的太差,累计的过程有点像动态规划,可以从右到左叠加0的个数来统计
于是改成了
代码: 全选
int count_pair2(vector<int> &arr, int begin, int end )
{
register int zero = 0, pair = 0;
for (register int id = end; id >= begin; id--)
arr[id] == 0 ? zero++ : pair += zero;
return pair;
}
测试代码:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int count_pair1(vector<int> &arr, int offset, int len );
int count_pair2(vector<int> &arr, int offset, int len );
int main(int argc, char *argv[] )
{
vector<int> arr{1,1,1,0,0, 0,1,1,0,0};
//arr = {1,1,0,1,0,1, 0,0,1,0,0,0};
int len = arr.size();
cout << count_pair1( arr, 0, len-1 ) << endl;
cout << count_pair2( arr, 0, len-1 ) << endl;
int L = count_pair2( arr, 0, len/2-1 );
int R = count_pair2( arr, len/2, len-1 );
cout << L << ", " << R << endl;
return 0;
}
int count_pair2(vector<int> &arr, int begin, int end )
{
register int zero = 0, pair = 0;
for (register int id = end; id >= begin; id--)
arr[id] == 0 ? zero++ : pair += zero;
return pair;
}
int count_pair1(vector<int> &arr, int begin, int end )
{
register int pair = 0;
register int L, R;
for (L = begin; L < end; L++)
for (R = L+1; R <= end; R++)
if ( arr[L] > arr[R] )
pair++;
return pair;
}