最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

世界新消息丨AT_abc297_e 题解

来源：博客园

一、题目描述：　　给你 n 个正整数，求这些数能凑成的第 k 大的数字（如果多种方式凑成同一个数，只算一次）。每个数可以选择无限次，且至少选择一个数。n<=10，k<=2e5 。


(资料图片仅供参考)

二、解题思路：

一开始想了好多错误思路。（话说这个题学校 OJ 上是不是遇到过，怎么感觉这么熟悉？）

很容易想到有用一个优先队列或者 set 之类的东西来存数。set 自带去重，所以我选了 set 。

每次选择最优的一个数 x ，对他进行拓展。枚举n 个数中的每一个数，设为 $a_i$ 。

在 set 中加入 x+$a_i$，最后从 set 中删去 x ，就完成了对 x 的拓展。

一个数必然可以由某个数加上 n 个数中的一个数得到。保证每个数都能被拓展到。

循环 k 次就可以了，时间复杂度 O(nk+klog(nk))，可以接受。

三、完整代码：

1 #include 2 #include 3 #define ll long long 4 using namespace std; 5 ll n,k,x,last,a[20]; 6 set  s; 7 int main() 8 { 9     cin>>n>>k;10     for(int i=1;i<=n;i++)11         cin>>a[i],s.insert(a[i]);12     for(int i=1;i<=k;i++)13     {14         x=*s.begin();15         s.erase(s.begin());16         for(int j=1;j<=n;j++)17             s.insert(x+a[j]);18     }19     cout<
四、写题心得：
很难想象 E 题代码居然这么短。不过是好事，我就喜欢短代码。加油！拜拜！
                 

关键词：