題意：
? ? ? 給你一個集合，讓你從里面找到4個元素，使得a+b+c=d,并且找到最大的d。


思路：
? ? ? 我們可以吧問題拆開，使得a+b=d-c,這樣就能O(n^2)枚舉a+b記錄出現的和，然后在同樣枚舉d-c如果出現過并且不沖突，就更新答案，這個方法在白書里叫做什么中途相遇法，其實就是雙向廣搜的那個思路，我是開了兩個容器，mkc[aaa]表示的是aaa出現了幾次，aaa是a+b,另一個容器是mark[s][now] 表示的是s這個和（前面枚舉的a+b）的其中一個加數是否是now，然后枚舉tmp = d-c,如果mkc[tmp]>1出現過不止一次，或者mkc[tmp]=1,只出現了一次并且mark[tmp][a] != 1 && mark[tmp][b] != 1就是這個和的兩個加數不是d,也不是c，就可以更新組大的d了，這樣還是超時了，估計是容器那弄的，然后我們在枚舉d的時候還有一個小技巧，就是先排序，然后從最大的d開始枚舉，如果找到一個答案就直接break，這樣能節省點時間，就可以AC了，如果還有不清楚的，具體細節看下面代碼。




#include<map>
#include<stdio.h>
#include<string.h>
#include<algorithm>?


using namespace std;


map<int ,int>mkc;
map<int ,map<int ,int> >mark;


int num[1100];


bool camp(int a, int b)
{
? ?return a > b;
}


int main ()
{
? ? int n ,i ,j;
? ? while(~scanf("%d" ,&n) && n)
? ? {
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? scanf("%d" ,&num[i]);
? ? ? ? if(n < 4)
? ? ? ? {
? ? ? ? ? ? ?puts("no solution");
? ? ? ? ? ? ?continue;
? ? ? ? ?}
? ? ? ? mkc.clear();
? ? ? ? mark.clear();
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? for(j = i + 1 ;j <= n ;j ++)
? ? ? ? {
? ? ? ? ? ?int s = num[i] + num[j];
? ? ? ? ? ?mkc[s] ++;
? ? ? ? ? ?mark[s][num[i]] = mark[s][num[j]] = 1;
? ? ? ? }
? ? ? ? sort(num + 1 ,num + n + 1 ,camp);
? ? ? ? int Ans = -1000000000;
? ? ? ? for(i = 1 ;i <= n && Ans == -1000000000;i ++)
? ? ? ? for(j = n ;j >= 1 && Ans == -1000000000;j --)
? ? ? ? {
? ? ? ? ? ?if(i == j) continue;
? ? ? ? ? ?int c = num[i] - num[j];
? ? ? ? ? ?if(mkc[c] > 1 || mkc[c] == 1 && !mark[c][num[j]] && !mark[c][num[i]])
? ? ? ? ? ?{
? ? ? ? ? ? ? ?if(Ans < num[i]) Ans = num[i];
? ? ? ? ? ?} ? ? ??
? ? ? ? }
? ? ? ? if(Ans == -1000000000) puts("no solution");
? ? ? ? else printf("%d\n" ,Ans);
? ? }
? ? return 0;
}
? ? ? ??
? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ??
? ? ? ??
? ? ? ??
? ? ? ??
? ? ? ??
? ? ? ??
? ? ? ??
? ? ? ??
? ? ? ??
? ??
? ??
? ??

總結

以上是生活随笔為你收集整理的UVA10125和集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。