1474 - C. Array Destruction (set、思维)

深碍√TFBOYSˉ_ 2021-07-17 01:37 336阅读 0赞

[题目][Link 1]

思路：可以知道一开始所选的两个数一定要包含最大的一个，假如不包含，那么后面的任何一个数加上最大的那个不可能构成另一个数，按着这个思路走下去，后面的每一步都需要包含还剩下的数中最大的数，如果不包含，理由同上，不可能继续构造下去。所以现在我们只需枚举一开始每一个数当成最初和最大数一起排除出去的即可，细节见代码。

Code:

#include<iostream>
    #include<set>
    #include<vector>
    using namespace std;
    typedef long long ll;
    const int Max = 2e6 + 5;
    int lst[Max];
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		multiset<int> set, st;
    		vector<int> ans;
    		int n;cin >> n;
    		for (int i = 1;i <= 2 * n;i++) {  int a;cin >> a;lst[i] = a;set.insert(a); }
    		for (int i = 1;i <= 2*n;i++)
    		{ 
    			vector<int> vec;
    			st = set;int sum = lst[i] + *st.rbegin();
    			int f = 1;
    			while (st.size())
    			{ 
    				auto x = st.end();x--;
    				auto y = st.find(sum - *x);
    				if (y == st.end() || x == y) {  f = 0;break; }
    				vec.push_back(*x);vec.push_back(*y);
    				sum = max(*x, *y);
    				st.erase(x);st.erase(y);
    			}
    			if (f) {  ans = vec; break; }
    		}
    		if (ans.size())
    		{ 
    			cout <<"YES"<<endl<< ans[0] + ans[1] << endl;
    			for (int i = 0;i < n;i++)cout << ans[2 * i] << " " << ans[2 * i + 1] << endl;
    		}
    		else cout << "NO" << endl;
    	}
    }

[Link 1]: https://codeforces.ml/contest/1474/problem/C

发表评论取消回复

表情：

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

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

相关阅读

相关 Java Array、List、Set互相转化

Java Array、List、Set互相转化 1. Array、List、Set互转实例 1.1 Array、List互转 Array转List Str

太过爱你忘了你带给我的痛/ 2023年10月11日 16:10/ 0 赞/ 43 阅读

相关 Beauty of Array————思维(或者DP)

Beauty of Array Time Limit: 2 Seconds Memory Limit: 65536 KB Edward has an array A

心已赠人/ 2022年04月23日 21:18/ 0 赞/ 159 阅读

相关魔术方法（一）construct,destruct

通常以\_\_(两个下划线)开始，并且不需要显示的调用而是由某种特定的条件触发，具有某些特殊的功能和要求，新版本15个魔术方法。一、构造函数 1、\_\_cons

本是古典何须时尚/ 2022年02月26日 01:08/ 0 赞/ 230 阅读

相关 HDU problem 5635 LCP Array【思维】

LCP Array Accepts: 131 Submissions: 1352 Time Limit: 4000/2000 MS (Java/Others)

谁借莪１个温暖的怀抱￠/ 2022年01月10日 04:37/ 0 赞/ 175 阅读

相关 JavaScript集合类：Array、Map、Set

版权声明：本文为博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/cathar

谁借莪１个温暖的怀抱￠/ 2021年10月15日 20:23/ 0 赞/ 382 阅读

相关 Set 和 Array

> ES6 提供了一个新的数据结构 Set 用来存储任意类型的值，它类似于数组。转换 Array 转换成 Set let arr = [1, 2,

ゝ一纸荒年。/ 2021年09月19日 00:10/ 0 赞/ 386 阅读

相关 1474 - C. Array Destruction (set、思维)

[题目][Link 1] 思路：可以知道一开始所选的两个数一定要包含最大的一个，假如不包含，那么后面的任何一个数加上最大的那个不可能构成另一个数，按着这个思路走下去，后面

深碍√TFBOYSˉ_/ 2021年07月17日 01:37/ 0 赞/ 337 阅读

相关 D. A Leapfrog in the Array （思维）

[题目][Link 1] 思路：经过模拟可以发现对于一个元素的移动每次移动量是之前一次的两倍，如果将列表倒过来从0开始，那么每次元素的位置移动便是x=2x+1，现在给出了

冷不防/ 2021年07月16日 21:55/ 0 赞/ 363 阅读

相关 C. Two Arrays (dp、思维)

[题目][Link 1] a\[i\]\[j\] 表示前i个数字中第i个数字为j的所有情况的非递减序列的数目 b\[i\]\[j\] 表示前i个数字中第i个数字为j

浅浅的花香味﹌/ 2021年07月16日 19:19/ 0 赞/ 471 阅读

相关 F. Equalize the Array (map、思维)

[题目][Link 1] 思路：看一个例子 x:y 表示拥有x个相同的数有y个(2:3 1 1 2 2 3 3) 现在有 4:5 3:3 1:8 即

た入场券/ 2021年07月16日 13:38/ 0 赞/ 397 阅读