[TIOJ] 1062. 用餐地點(Lunch)

題目連結:http://tioj.infor.org/problems/1062

---

這題題目好像有點怪，但還在可理解的範圍內，總之就是問你說給你網格內的一堆數，每個人移動都有1單位的cost，問你選哪個點讓大家都移動到他後的cost最小。
可以發現其實左右跟上下是可以分開的，因為他不能斜的走。所以就從左到右枚舉哪個點可以並從上到下枚舉哪個點可以，兩個混和在一起就好了。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<lld, int> PLI;
#define FF first
#define SS second
const int N = 100 + 5;
const lld INF = 1LL<<60;

lld X[N], Y[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m; cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x; cin>>x;
			X[j]+=x;
			Y[i]+=x;
		}
	}
	PLI ansX={INF, 0}, ansY={INF, 0};
	lld curX=0, curY=0;
	for(int i=1;i<=m;i++) curX+=X[i]*i;
	for(int i=1;i<=n;i++) curY+=Y[i]*i;
	for(int i=1;i<=m;i++) X[i]+=X[i-1];
	for(int i=1;i<=n;i++) Y[i]+=Y[i-1];
	for(int i=1;i<=m;i++){
		curX += X[i-1];
		curX -= X[m]-X[i-1];
		if(curX < ansX.FF) ansX = {curX, i};
	}
	for(int i=1;i<=n;i++){
		curY += Y[i-1];
		curY -= Y[n]-Y[i-1];
		if(curY < ansY.FF) ansY = {curY, i};
	}
	cout<<ansY.SS<<' '<<ansX.SS<<'\n';
	return 0;
}