题解 | #素数伴侣#c++#acm模式
素数伴侣
http://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e
#include <iostream> #include <vector> using namespace std; bool isPrime(int num) { if( 1 == num ) return false; for( int i = 2; i*i <= num; i++ ) { if( num % i == 0) return false; } return true; } bool match(int x, vector<int> evens, vector<bool>& vis, vector<int>& evensMatch) { // 遍历偶数,检查当前传入的奇数和那些偶数匹配 for( int i = 0; i < evens.size(); i++ ) { // 如果当前偶数与传入的奇数匹配,且该偶数还没有匹配过奇数 if( isPrime(x + evens[i]) && !vis[i] ) { vis[i] = true; if( evensMatch[i] == 0 || match(evensMatch[i], evens, vis, evensMatch) ) { evensMatch[i] = x; // 传入的奇数可以作为第 i 个偶数的伴侣 return true; } } } // 遍历完偶数都没有找到匹配得到的,返回匹配失败 return false; } int main() { int n; while( cin >> n ) { vector<int> odds, evens; // 奇数和偶数 int tmp; for( int i = 0; i < n; i++ ) { cin >> tmp; if( tmp & 1 == 1 ) odds.push_back(tmp); else evens.push_back(tmp); } // 标记偶数和那个奇数匹配了,并记录该奇数的值 vector<int> evensMatch(evens.size(), 0); int res = 0; for( int i = 0; i < odds.size(); i++ ) { vector<bool> vis(evens.size(), false); if( match(odds[i], evens, vis, evensMatch) ) res++; } cout << res << endl; } return 0; }