codefun/Meeting_Point.cpp at master · whodewho/codefun · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include "stdafx.h"
#include "iostream"
#include "vector"
#include "string"
#include "map"
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <stack>
#include <sstream>
#include <iomanip>
#include <random>
#include <assert.h>
#include <iterator>
#include <queue>
#include <math.h>
#include <vector>

using namespace std;

vector<int> meetPoint(int matrix[3][4], int m, int n)
{
	vector<int> result;

	vector<int> row(m, 0);
	vector<int> col(n, 0);
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(matrix[i][j])
			{
				row[i]=matrix[i][j];
				col[j]=matrix[i][j];
			}
		}
	}

	int leftPeopleNum=0, leftWalkSum=0, rightPeopleNum=0, rightWalkSum=0;
	int i=0, j=m-1;
	while(i<j)
	{
		if(leftPeopleNum+row[i]<=rightPeopleNum+row[j])
		{
			leftPeopleNum+=row[i];
			leftWalkSum=leftWalkSum+leftPeopleNum;
			i++;
		}
		else
		{
			rightPeopleNum+=row[j];
			rightWalkSum=rightWalkSum+rightPeopleNum;
			j--;
		}
	}
	result.push_back(i);

	int upPeopleNum=0, upWalkSum=0, downPeopleNum=0, downWalkSum=0;
	i=0,j=n-1;
	while(i<j)
	{
		if(upPeopleNum+col[i]<=downPeopleNum+col[j])
		{
			upPeopleNum+=col[i];
			upWalkSum=upWalkSum+upPeopleNum;
			i++;
		}
		else
		{
			downPeopleNum+=col[j];
			downWalkSum=downWalkSum+downPeopleNum;
			j--;
		}
	}
	result.push_back(j);
	return result;
}

void testMeetPoint()
{
	int a[3][4]={{0,4,0,0},{0,0,0,3},{5,0,0,0}};
	vector<int> result=meetPoint(a,3,4);
	cout<<result[0]<<" "<<result[1]<<endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	testMeetPoint();
	return 0;
}