点击刷新
题意：
给你一个集合，让你从里面找到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;
}
给你一个集合，让你从里面找到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;
}
© 著作权归作者所有
举报
相关热门文章
发表评论
0/200
