前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >codeforces 305 C. Ivan and Powers of Two

codeforces 305 C. Ivan and Powers of Two

作者头像
xindoo
发布2021-01-21 18:36:42
3620
发布2021-01-21 18:36:42
举报
文章被收录于专栏:XINDOO的专栏XINDOO的专栏

题目链接

给出一个非减序的数组a[n], 然后得到s=2^a1+.……+2^an, 要使s为2^v -1,需要在数组中添加几个数。

我的思路是这样的,由2^a+2^a = 2^(a+1)可知,如果有两个连续的数a,我们可以把他们合并为a+1放入集合中,使集合中没有重复的数,我可以用stl里的set。如果想要满足题目中的要求,集合中必须有最大那个数个元素,缺多少就可以计算出来了。

代码:

代码语言:javascript
复制
//codeforces 305 C. Ivan and Powers of Two
//2013-06-05-17.19
#include <stdio.h>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;
set<int> s;
int main()
{
    int n, a;
    while (scanf("%d", &n) != EOF)
    {
        s.clear();
        int maxn = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a);
            while (s.count(a))
            {
                s.erase(a);
                a++;
            }
            s.insert(a);
            maxn = max(a, maxn);
        }
        printf("%d\n", maxn-s.size()+1);
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2013-06-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档