C. Going Home （抽屉原理、范围、暴力）

Bertha 。 2021-09-07 06:18 275阅读 0赞

[题目][Link 1]

[抽屉原理][Link 2]

看题目的数据，其中可以发现两个数相加结果最大也只是5e6，根据抽屉原理，只要有5e6+1个数就至少会有两个数相加得到相同的值。那么也就是说只要枚举出来的两个数相加的答案最多有5e6+1个就一定会得到至少两组坐标满足相加相等，直接暴力即可。

#include<iostream>
    using namespace std;
    typedef long long ll;
    const int Max = 5e6 + 5;
    int lst[Max];
    int ls[Max][2];
    int main()
    { 
    	int n;cin >> n;
    	for (int i = 1;i <= n;i++)cin >> lst[i];
    	for (int i = 1;i < n;i++)
    	{ 
    		for (int j = i + 1;j <= n;j++)
    		{ 
    			int sum = lst[i] + lst[j];
    			if (ls[sum][0] != 0&&ls[sum][1]!=i&&ls[sum][1]!=j&&ls[sum][0]!=i)
    			{ 
    				cout << "YES" << endl;
    				cout << ls[sum][0] << " " << ls[sum][1] << " " << i << " " << j;
    				return 0;
    			}
    			else ls[sum][0] = i, ls[sum][1] = j;
    		}
    	}
    	cout << "NO" << endl;
    }

[Link 1]: https://codeforc.es/contest/1501/problem/C
[Link 2]: https://blog.csdn.net/wentong_Xu/article/details/81662987?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161589297016780269821692%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=161589297016780269821692&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~rank_v29-6-81662987.first_rank_v2_pc_rank_v29&utm_term=%E6%8A%BD%E5%B1%89%E5%8E%9F%E7%90%86

发表评论取消回复

表情：

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

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

相关阅读

相关【Go】Go 语言教程--Go 语言范围(Range)（十五）

往期回顾： [Go 语言教程–介绍（一）][Go] [Go 语言教程–语言结构（二）][Go 1] [Go 语言教程–语言结构（三）][Go 2] [

心已赠人/ 2023年10月13日 17:48/ 0 赞/ 54 阅读

相关 android 抽屉_Android导航抽屉教程

![c0ebdc8967049202797d383f886bf329.png][] android 抽屉 In this tutorial you will learn a

r囧r小猫/ 2022年12月08日 04:46/ 0 赞/ 275 阅读

相关组合数学-抽屉原理

文章目录抽屉原理例题 HDU-1205 POJ-2356 抽屉原理 -------------------- 抽屉原理

迷南。/ 2022年11月28日 13:19/ 0 赞/ 293 阅读

相关抽屉原理……

第一抽屉原理原理1：把多于n个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。抽屉原理抽屉原理证明（反证法）：如果每个抽屉至多只能放进一个物

桃扇骨/ 2022年09月11日 01:27/ 0 赞/ 175 阅读

相关抽屉效果

[SlideringDrawer的使用(抽屉效果)][SlideringDrawer][http://www.itlanbao.com/code/20150825/10000

喜欢ヅ旅行/ 2022年07月26日 11:24/ 0 赞/ 171 阅读

相关 POJ-3370 Halloween treats （抽屉原理）

Every year there is the same problem at Halloween: Each neighbour is only willing to giv

本是古典何须时尚/ 2022年06月12日 05:43/ 0 赞/ 129 阅读

相关 HDU 4775 Infinite Go（暴力模拟+BFS）

　　Go is a proverbial board game originated in China. It has been proved to be the most d

超、凢脫俗/ 2022年06月09日 06:17/ 0 赞/ 166 阅读

相关 P2733 家的范围 Home on the Range

[https://www.luogu.org/problemnew/show/2733][https_www.luogu.org_problemnew_show_2733]

心已赠人/ 2022年06月06日 11:28/ 0 赞/ 74 阅读

相关 C. Going Home （抽屉原理、范围、暴力）

[题目][Link 1] [抽屉原理][Link 2] 看题目的数据，其中可以发现两个数相加结果最大也只是5e6，根据抽屉原理，只要有5e6+1个数就至少会有两个数

Bertha 。/ 2021年09月07日 06:18/ 0 赞/ 276 阅读

相关重构-抽屉(左右抽屉)

动画: 抽屉出现背景渐变抽屉出现消失移动动画实现: display从none到block产生过渡动画:使用anim

妖狐艹你老母/ 2021年07月24日 16:52/ 0 赞/ 440 阅读