【1-n】区间覆盖 TOJ4168+BZOJ1192
Xiao Ming is very interesting for array. He given a sorted positive integer array and an integer n.
We need add elements to the array such that the sum of subset of array cover the range [1, n]. You must return the minimum number of add elements.
Xiao Ming worry about you can't understand this problem. Now, he gives you an example:
There is an array [1, 3], n = 6, the answer is 1. Because we only need to add 2 into array. After add operator, the array is [1,2,3]. The subsets are: [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
Input
The input consists of multiple test cases. The first line contains an integer TT
, indicating the number of test cases.
Each case contains two integers m,nm,n
, mm
means the number of elements in array, nn
means the cover range.(1≤m≤105,1≤n≤2147483647)(1≤m≤105,1≤n≤2147483647)
.
Then comes a line with mm
integers.
Output
Return the minimum number of add elements.
Sample Input
1
3 20
1 5 10
Sample Output
2
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long num[100861];
int main()
{
int T;
for(scanf("%d",&T);T--;){
long long n,m;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld",num+i);
sort(num+1,num+1+n);
long long sum=0;
int ct=0,pos=1;
for(long long i=1;i<=m;++i)
{
if(num[pos]<=i&&pos<=n) {
sum+=num[pos];
++pos;
i=sum;
}
else {
++ct;
sum+=i;
i=sum;
}
}
printf("%d\n",ct);
}
}
1192: [HNOI2006]鬼谷子的钱袋
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3752 Solved: 2705
[Submit][Status][Discuss]
Description
鬼谷子非常聪明,正因为这样,他非常繁忙,经常有各诸侯车的特派员前来向他咨询时政。有一天,他在咸阳游历的时候,朋友告诉他在咸阳最大的拍卖行(聚宝商行)将要举行一场拍卖会,其中有一件宝物引起了他极大的兴趣,那就是无字天书。但是,他的行程安排得很满,他他已经买好了去邯郸的长途马车标,不巧的是出发时间是在拍卖会快要结束的时候。于是,他决定事先做好准备,将自己的金币数好并用一个个的小钱袋装好,以便在他现有金币的支付能力下,任何数目的金币他都能用这些封闭好的小钱的组合来付账。鬼谷子也是一个非常节俭的人,他想方设法使自己在满足上述要求的前提下,所用的钱袋数最少,并且不有两个钱袋装有相同的大于1的金币数。假设他有m个金币,你能猜到他会用多少个钱袋,并且每个钱袋装多少个金币吗?
Input
包含一个整数,表示鬼谷子现有的总的金币数目m。其中,1≤m ≤1000000000。
Output
只有一个整数h,表示所用钱袋个数
Sample Input
Sample Output
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
long long sum=0,m,ans=1,ct,tt=0;
scanf("%lld",&m);
while(1)
{
if(sum+ans>m) break;
sum+=ans;
ans<<=1;
++tt;
}
ct=m-sum;
if(!ct) printf("%lld\n",tt);
else printf("%lld\n",tt+1);
}
最新文章
- HTML标签marquee实现滚动效果
- 重启猫(modem)的方法
- HackerRank ";AND xor OR";
- java url中文 编译和解码
- bzoj2011: [Ceoi2010]Mp3 Player
- c#利用WebClient和WebRequest获取网页源代码
- Kali for Android
- [KMP][HDU3336][Count the string]
- Flex移动应用程序开发的技巧和窍门(五)
- Mac 上 Charles 抓取 iso http、https数据包
- EF-CodeFirst-基础
- 优雅地记录Python程序日志1:logging模块简介
- spring boot 事务支持
- Introducing Project Kinect for Azure
- error TRK0002: Microsoft Visual Studio 10.0\VC\bin\link.exe Access is denied.
- linux vnc 安装
- Chapter 3 Phenomenon——3
- 【R】用 ggplot2 绘制漂亮的分级统计地图
- 选择器(UIPickerView)
- Python文件传输模块ftplib