程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 11012 - Cosmic Cabbages(暴力)

uva 11012 - Cosmic Cabbages(暴力)

編輯:C++入門知識

題目連接:uva 11012 - Cosmic Cabbages


題目大意:給出n個三維坐標,輸出兩兩間曼哈頓距離最大的值。


解題思路:|xi - xj| + |yi - yj| + |zi - zj| = (+/-xi +/- yi +/- zi) - (+/-xj +/- yj +/- zj).

枚舉8種情況即可。


#include 
#include 
#include 

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 100005;

int n, x[N], y[N], z[N];

void init() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d%d%d", &x[i], &y[i], &z[i]);
}

inline int sign(int k) {
	return k ? -1 : 1;
}

int solve() {
	int ans = 0;
	for (int i = 0; i < 8; i++) {
		int Max = -INF, Min = INF;
		for (int j = 0; j < n; j++) {
			int k = x[j] * sign(i&4) + y[j] * sign(i&2) + z[j] * sign(i&1);	
			Max = max(k, Max);
			Min = min(k, Min);
		}	
		ans = max(ans, Max - Min);
	}
	return ans;
}

int main() {
	int cas;
	scanf("%d", &cas);
	for (int i = 1; i <= cas; i++) {
		init();
		printf("Case #%d: %d\n", i, solve());
	}
	return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved