怎样提高网站权重,线上营销渠道,太原seo服务,网站设计好了如何上传到自己搭建的网上去Description MK和他的小伙伴们#xff08;共n人#xff0c;且保证n为2的正整数幂#xff09;想要比试一下谁更有节操#xff0c;于是他们组织了一场节操淘汰赛。他们的比赛规则简单而暴力#xff1a;两人的节操正面相撞#xff0c;碎的一方出局#xff0c;而没碎的一方晋…
Description MK和他的小伙伴们共n人且保证n为2的正整数幂想要比试一下谁更有节操于是他们组织了一场节操淘汰赛。他们的比赛规则简单而暴力两人的节操正面相撞碎的一方出局而没碎的一方晋级脑补一下端午节的碰鸡蛋游戏_。最后经过数轮淘汰决出冠军“节操大师”。
通过理性的研究你测算出他们的节操值分别为1,2,...,n我们不妨称这个值为“硬度”吧。同时你又测出了一个节操常数k当两个硬度相差超过k的节操相撞时硬度小的节操必碎而当两个硬度相差不超过k的节操相撞时由于现场操作的不确定因素两个节操都有碎的可能当然我们假设不会出现两边都碎的情况囧。
显然节操值较低的人也许没有任何可能得到冠军。下面就请你预测这次比赛的冠军“节操大师”的节操最小值为多少。
Input
输入只有一行两个正整数n和k分别表示参赛人数和节操常数。
Output
输出一行一个正整数表示“节操大师”的节操最小值。
Sample Input
8 2
Sample Output
3
Hint
对20%数据n≤16;
对50%数据n≤4096;
对100%数据n≤131072, 保证n为2的正整数幂kn。
Source
Nankai UniversityFreshman Programming Contest 2015 题解这道题目很有意思两两相撞当节操差大于k时节操小的必碎否则的话两个都可能碎一次碰撞只能碎一个
我们采用二分答案的方法对于每一个答案ans我们判断它能否形成一个竞赛树自顶向下生成也就是逆向思考在考虑最后一轮对撞的时候
必然有ans与x对撞其中ans x 或者是x - ans k因为只有这样才有可能选上我们贪心地对于ans选取比ans大且ans可能战胜的最大的x如果不满足的话我们就选取第二大的x。。。。依次类推这样的话我们可以保证ans总是发挥了它最大的能力这样的话最有可能构成一个完全二叉树如果不能构成完全二叉树说明这个答案不合适 #include iostream
#include set
#include cstdio
#include vector
using namespace std;
int n,k;
bool check(int x)
{setint st;vectorint vec;vec.push_back(-x);for(int i 1;i n;i)if(i ! x)st.insert(-i);while(vec.size() ! n){int s vec.size();for(int i 0;i s;i){int v vec[i];auto np st.lower_bound(v - k);int y *np;if(np ! st.end()){vec.push_back(y);//st.erase(y);}elsereturn false;}}return true;
}
int main()
{scanf(%d%d,n,k);int l 1,r n 1;while(l r){int mid (lr)/2;if(!check(mid)) l mid 1;else r mid ;}coutlendl;
}