[UVa] 10125 - Sumsets

題目網址: http://goo.gl/Lu96vI

題 意: 給大小為 n (1 <= n <= 1000) 的集合，求滿足 a + b + c = d ， a、b、c、d 皆為集合內元素，最大的 d。


解法: 將 a + b + c = d 拆解成 a + b = d - c，接著算出 a + b 的數列，再枚舉 d -c 在 a + b 數列二分找是否存在即可。

TAG: ad hoc, binary search,

注意:

程式碼:

	/**
	* Tittle: 10125 - Sumsets
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/31
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	#include <vector>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 1005
	typedef long long ll;
	class Sum {
	public:
	ll val;
	int a, b;
	Sum( ll _v=0LL, int _a=0, int _b=0 ):
	val(_v), a(_a), b(_b) {}
	const bool operator<( const Sum &op ) const {
	return val < op.val;
	}
	};
	typedef vector<Sum> VS;
	// declarations
	int n;
	ll elm[N];
	VS sum;
	// functions
	ll solve( void )
	{
	VS::iterator it;
	for( int i=n; i>=1; --i ) FOR( j, 1, n ) {
	if( i==j ) continue;
	it = lower_bound( sum.begin(), sum.end(), Sum(elm[i]-elm[j]) );
	if( (*it).val == (elm[i]-elm[j]) ) {
	if( (*it).a==i || (*it).b==i ) continue;
	if( (*it).a==j || (*it).b==j ) continue;
	return elm[i];
	}
	}
	return -536870913LL;
	}
	// main function
	int main( void )
	{
	ll maxe;
	// input
	while( scanf( "%d", &n )==1 && n ) {
	FOR( i, 1, n ) scanf( "%lld", &elm[i] );
	sort( elm+1, elm+1+n );
	// init
	sum.clear();
	// solve
	FOR( i, 1, n ) FOR( j, i+1, n ) {
	sum.push_back( Sum(elm[i]+elm[j],i,j) );
	}
	sort( sum.begin(), sum.end() );
	maxe = solve();
	if( maxe == -536870913LL ) puts("no solution");
	else printf( "%lld\n", maxe );
	}
	return 0;
	}

view raw 10125 - Sumsets.cpp hosted with ❤ by GitHub