Poj 2549 Sumsets (3Sum问题)

灰太狼 2022-08-25 15:55 121阅读 0赞

题意：给出一个数集，问其中是否存在a,b,c,d满足a+b+c=d，输出最大的d

理论学习：http://blog.csdn.net/doc\_sgl/article/details/12462151

http://tech-wonderland.net/blog/summary-of-ksum-problems.html

也可以将问题转化为a+b=d-c，将左侧计算出之后，枚举右边用Hash解决

可以参考：http://wingszero.blogbus.com/logs/80205824.html

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int n,data[1005];
    
    int main ()
    {
    	while (scanf("%d",&n),n)
    	{
    		int ans,i;
    		bool flag=true;
    		for (i=0;i<n;i++)
    			scanf("%d",&data[i]);
    		sort(data,data+n);
    		int sz = unique(data,data+n)-data;  //去重
    		n=sz;
    		for (int d=n-1;d>=0 && flag;d--)    //枚举d
    			for (i=0;i<n-3 && flag;i++)     //注意因为有负数存在,需要扫完全部
    			{
    				int head=i+1,tail=n-1;   //从首尾两个方向扫描
    				while (head<tail)
    				{
    					int tmp=data[i]+data[head]+data[tail];
    					if (tmp==data[d])
    					{
    						if (i==d || head==d || tail==d) break;
    						flag=false;
    						ans=tmp;
    						break;
    					}
    					else if (tmp>data[d]) tail--;
    					else head++;
    				}
    			}
    		if (flag)
    			printf("no solution\n");
    		else
    			printf("%d\n",ans);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，121人围观）

还没有评论，来说两句吧...

相关阅读

相关凎！一个函数秒杀 2Sum 3Sum 4Sum 问题

点击上方“五分钟学算法”，选择“星标”公众号重磅干货，第一时间送达![format_png][] ![format_png 1][]来源：labuladong 经常刷

r囧r小猫/ 2023年02月25日 07:20/ 0 赞/ 16 阅读

相关 3 Sum问题

3 Sum 问题题目链接：lintcode 3 sum ([http://www.lintcode.com/en/problem/3sum/][http_www.lin

不念不忘少年蓝@/ 2022年09月25日 00:28/ 0 赞/ 112 阅读

相关 Poj 2549 Sumsets (3Sum问题)

题意：给出一个数集，问其中是否存在a,b,c,d满足a+b+c=d，输出最大的d 理论学习：http://blog.csdn.net/doc\_sgl/article/det

灰太狼/ 2022年08月25日 15:55/ 0 赞/ 122 阅读

相关 2sum问题和3sum问题

算法这个书，190页介绍了这两个问题。 2sum的意思是在一组数中，找到两个数的和为零。有多少个这样的组合。 3sum是找有多少三个数的组合，他们的和为零

╰+攻爆jí腚メ/ 2022年08月20日 09:29/ 0 赞/ 126 阅读

相关 Sumsets（4sum问题）

Sumsets <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

梦里梦外;/ 2022年08月01日 18:06/ 0 赞/ 122 阅读

相关 3Sum

题目 Given an array S of n integers, are there elements a, b, c in S such that a \+ b \

灰太狼/ 2022年06月07日 13:16/ 0 赞/ 112 阅读

相关 POJ 2229 Sumsets（基础dp）

Sumsets <table> <tbody> <tr> <td><strong>Time Limit:</strong> 2000MS</td>

秒速五厘米/ 2022年06月07日 05:45/ 0 赞/ 124 阅读

相关 3-sum问题

3-sum问题：统计一个不重复数组中3个数相加为0的组合。 import java.util.Arrays; public class Main {

快来打我*/ 2022年06月06日 12:16/ 0 赞/ 127 阅读

相关 POJ 2479 Maximum sum

Maximum sum Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 42643 Accepte

迈不过友情╰/ 2022年05月28日 05:36/ 0 赞/ 76 阅读

相关 POJ 2229 Sumsets————（完全背包 or 规律）

Sumsets Time Limit: 2000MS Memory Limit: 200000K Total Submissions: 23184 Accepted:

男娘i/ 2022年05月18日 04:36/ 0 赞/ 119 阅读