CodeForces-916B-Jamie and Binary Sequence(changed after round)(构造)
链接:
https://vjudge.net/problem/CodeForces-916B
题意:
Jamie is preparing a Codeforces round. He has got an idea for a problem, but does not know how to solve it. Help him write a solution to the following problem:
Find k integers such that the sum of two to the power of each number equals to the number n and the largest integer in the answer is as small as possible. As there may be multiple answers, you are asked to output the lexicographically largest one.
To be more clear, consider all integer sequence with length k (a1, a2, ..., ak) with . Give a value to each sequence. Among all sequence(s) that have the minimum y value, output the one that is the lexicographically largest.
For definitions of powers and lexicographical order see notes.
思路:
先构造出最少数量的序列,如果此时长度大于m,就是没有可能.
否则优先判断前面较大的能不能全部用掉,否则从小的开始去减.
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
//#include <memory.h>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
#include <stack>
#include <string>
#include <assert.h>
#include <iomanip>
#define MINF 0x3f3f3f3f
using namespace std;
typedef long long LL;
LL n, m;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
multiset<int> st;
for (int i = 63;i >= 0;i--)
{
if ((1ULL<<i) <= n)
{
st.insert(i);
n -= (1LL<<i);
}
}
if (st.size() > m)
puts("No");
else
{
while (st.size() < m)
{
if (st.size() == 1)
{
int t = *st.rbegin();
st.erase(*st.rbegin());
st.insert(t-1);
st.insert(t-1);
}
else
{
int cnt = st.count(*st.rbegin());
if (m-st.size() >= cnt)
{
int t = *st.rbegin();
st.erase(t);
for (int i = 1;i <= cnt*2;i++)
st.insert(t-1);
}
else
{
int t = *st.begin();
t--;
st.erase(st.begin());
while (st.size()+2 < m)
{
st.insert(t);
t--;
}
st.insert(t);
st.insert(t);
}
}
}
cout << "Yes" << endl;
for (multiset<int>::reverse_iterator it = st.rbegin();it != st.rend();++it)
cout << *it << ' ';
cout << endl;
}
return 0;
}
最新文章
- 【Network】修改docker启动默认网桥docker0为自定义网桥
- array_filter、array_map、array_walk解释
- Intent官方教程(4)用Intent构造应用选择框
- sql新增后返回主键
- How many - HDU 2609 (trie+最小表示)
- 《30天自制操作系统》读书笔记(3) 引入C语言
- C#实现测量程序运行时间及cpu使用时间
- 1622: [Usaco2008 Open]Word Power 名字的能量
- Go语言学习笔记(八)golang 操作 Redis &; Mysql &; RabbitMQ
- 【原创】源码角度分析Android的消息机制系列(五)——Looper的工作原理
- [HNOI2009]无归岛
- css选择器语法速查
- selenium:断言
- easyui 自动动态合并单元格
- webpack 优化
- express中间件--Morgan 日志记录
- SQLite之C#连接SQLite
- NHibernate出现could not execute query问题
- Python 基础语法——数字和表达式(包含数学上的一些函数)
- Metasploit 使用基础