信息学奥赛一本通（C++版） 第二部分 基础算法 第七章 分治算法
http://ybt.ssoier.cn:8088/
//1325 【例7.4】 循环比赛日程表
//http://blog.****.net/axiqia/article/details/50945510此文分析及代码写得真不赖
//https://www.cnblogs.com/liushang0419/archive/2011/09/19/2181402.html此文递归代码写得不错，虽然对不上题，但值得学习。
//本人更倾向于递归
//递归写下的代码十分顺手，样例通过，提交AC 2017-12-19
#include <stdio.h>
int table[110][110];
int f(int m){
int i,ans=1;
for(i=1;i<=m;i++)ans*=2;
return ans;
}
void fill_table(int x,int y,int step){
int i,j;
if(step==1)return;
step/=2;
fill_table(x,y,step),fill_table(x+step,y,step);//左上角，左下角
for(i=0;i<step;i++)
for(j=0;j<step;j++){
table[x+step+i][y+step+j]=table[x+i][y+j];//右下角等于左上角
table[x+i][y+step+j]=table[x+step+i][y+j];//右上角等于左下角
}
}
int main(){
int m,n,i,j;
scanf("%d",&m);
n=f(m);
for(i=1;i<=n;i++)table[i][1]=i;//第一列处理
fill_table(1,1,n);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
printf("%d ",table[i][j]);
printf("\n");
}
return 0;
}
1326 【例7.5】 取余运算（mod）
1.//p1226 取余运算||快速幂
http://blog.****.net/mrcrack/article/details/61625530
//很久以前接触过 快速幂 ，云里雾里
//这次翻看他人对快速幂的讲解，同时手动进行模拟，真的弄懂了。
//不容易，认识是螺旋式上升，第一次不懂，第二次似懂非懂，第三次弄懂，难能可贵
//提交，测试点4,5,6 WA
//下载 测试点4数据，之后将程序中的int 全改成long long 测试点4通过，提交AC
#include <stdio.h>
int main(){
long long b,p,k,ans=1,a,n;
scanf("%lld%lld%lld",&b,&p,&k);
n=p;
a=b;
while(n){
if(n&1)
ans=(ans*a)%k;
a=(a*a)%k;
n>>=1;
}
printf("%lld^%lld mod %lld=%lld\n",b,p,k,ans);
return 0;
}
//1327 【例7.6】黑白棋子的移动
//https://www.cnblogs.com/zzyh/p/6623490.html此文代码思路都写得不赖
//思路摘抄如下：
//我们先从n=4开始试试看，初始时：
// ○○○○●●●●
//第1步：○○○——●●●○● {—表示空位}
//第2步：○○○●○●●——●
//第3步：○——●○●●○○●
//第4步：○●○●○●——○●
//第5步：——○●○●○●○●
// 如果n=5呢？我们继续尝试，希望看出一些规律，初始时：
// ○○○○○●●●●●
//第1步：○○○○——●●●●○●
//第2步：○○○○●●●●——○●
// 这样，n=5的问题又分解成了n=4的情况，下面只要再做一下n=4的5个步骤就行了。同理，n=6的情况又可以分解成n=5的情况，……，所以，对于一个规模为n的问题，我们很容易地就把他分治成了规模为n-1的相同类型子问题。
//刚开始一点思路都没有觉得问题特别复杂，其实根据我做的这一丢丢题看来,步骤或者说是过程描述性强的题目，都有一定的规律，可用递归递推去做。
//这样的题一定有一定的规律，如当n=5时，再稍加变动就恢复n=4时的情况，这就是有规律可循了，问题就变得简单；再好比前面汉诺塔的题目，题目会仔细
//说明怎样去移动，那就有规律可循了，不多解释了，和这个题情况一样，又会恢复到n-1的状态；（快夸我！QWQ）
//初始化--输出--移动n个棋子（函数）--怎样移动（函数）--移动后输出（输出函数）
//提交，测试点3-4 格式错误，仔细对照样例
//7
//step 0:ooooooo*******--
//step 1:oooooo--******o*
//step 2:oooooo******--o*
//step 3:ooooo--*****o*o*
//step 4:ooooo*****--o*o*
//step 5:oooo--****o*o*o*
//step 6:oooo****--o*o*o*
//step 7:ooo--***o*o*o*o*
//step 8:ooo*o**--*o*o*o*
//step 9:o--*o**oo*o*o*o*
//step 10:o*o*o*--o*o*o*o*
//step 11:--o*o*o*o*o*o*o*
//上述输出，确实格式错误，请仔细对照 step 10 step 11与输入样例的差异
//修改，提交AC 2018-1-10
//样例通过，提交AC 2018-1-15 思路正确，步骤正确，编写程序正确。
#include <stdio.h>
int n,step=0,newp;//newp 当前第一个'-'位置
char c[1000];
void print(){//打印步骤
int i;
printf("step%2d:",step++);
for(i=1;i<=2*n+2;i++)printf("%c",c[i]);
printf("\n");
}
void init(){//初始化
int i;
for(i=1;i<=n;i++)c[i]='o';
for(i=n+1;i<=2*n;i++)c[i]='*';
for(i=2*n+1;i<=2*n+2;i++)c[i]='-';
newp=2*n+1;
}
void move(int m){//当前移动 m 当前移动的第一个棋子的位置在m
c[newp]=c[m],c[newp+1]=c[m+1],c[m]=c[m+1]='-',newp=m;//当前第一个'-'位置
print();
}
void design(int m){//当前规模 方案
if(m==4)move(4),move(8),move(2),move(7),move(1);
else move(m),move(2*m-1),design(m-1);//降低一个维度
}
int main(){
scanf("%d",&n);
init();
print();
design(n);
return 0;
}
//1328 【例7.7】光荣的梦想 2017-12-10 16:30
//1237 求排列的逆序数
//1311 【例2.5】求逆序对
//按冒泡思路编写，猜想，要超时，试试，看看数据水不水
//提交，果然超时，
//翻了之前的记录，发现是洛谷 P1908 逆序对 不过当时是用树状数组
//http://blog.****.net/mrcrack/article/details/61625530
//这次准备用归并排序做
//http://blog.****.net/yuehailin/article/details/68961304代码写得很对胃
//http://www.cnblogs.com/chengxiao/p/6194356.html用图分析归并排序算法过程，很清晰
//http://blog.****.net/acdreamers/article/details/16849761用归并排序求逆序对，关键点讲得好，摘抄如下：
//归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序，然后再将这两半合并起来。
//在合并的过程中（设l<=i<=mid，mid+1<=j<=h），当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在
//前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。因此，可以在归并
//排序中的合并过程中计算逆序数.
//样例通过，提交，未通过，
//同样的程序在洛谷里提交，AC，真是太奇葩了，洛谷 P1908 逆序对
//https://www.luogu.org/problemnew/show/P1908
//转念一想，可能是逆序对太多，int溢出，把int 改成long long 修改，提交AC 真不容易啊2017-10-28 22:26
//将int 改成 long long 整整用了17分钟
#include <stdio.h>
int a[100100],b[100100];
long long ans=0;////转念一想，可能是逆序对太多，int溢出，把int 改成long long
void memery_sort(int left,int mid,int right){//自小到大
int i=left,j=mid+1,n=mid,m=right,k=0;
while(i<=n&&j<=m)
if(a[i]>a[j]){
ans+=n-i+1;
b[k++]=a[j++];
}else
b[k++]=a[i++];
while(i<=n)b[k++]=a[i++];
while(j<=m)b[k++]=a[j++];
for(i=0;i<k;i++)a[left+i]=b[i];//1此处写成 for(i=1;i<k;i++)a[i]=b[i];
}
void merge_sort(int left,int right){
int mid=(left+right)/2;
if(left>=right)return ;
merge_sort(left,mid);
merge_sort(mid+1,right);
memery_sort(left,mid,right);
}
int main(){
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
merge_sort(0,n-1);
printf("%lld",ans);
return 0;
}
//1234 2011
//快速幂，对10000取余
//样例通过，提交，全部答案错误
//重新读题，发现n的最大长度为200位，直接用%d无法读取。即为该题错误原因。
//自认为高精度掌握还可以，上高精度除
//没想法了，程序编好，尽然样例一次性通过，提交AC，没做啥修改，看来高精度除低精度，写得十分顺畅
//水平提高，看得见，2017-11-22
#include <stdio.h>
#include <string.h>
char a[210];
int b[210];
void divide(){//高精度 除以 低精度
int i,ans;
for(i=b[0];i>=1;i--){
if(i>1)b[i-1]+=(b[i]%2)*10;
b[i]/=2;
}
i=b[0];
while(b[i]==0)i--;//去除多余的前导0
if(i==0)b[0]=1;
else b[0]=i;
}
int myPower(int c,int mod){
int ans=1;
while(!(b[0]==1&&b[1]==0)){//b[0]==0&&b[1]==0表示该数据为0
if(b[1]%2==1)//奇数
ans=(ans*c)%mod;//此处写成 ans*=(ans*a)%mod; 有失水准
c=(c*c)%mod;
divide();
}
return ans;
}
int main(){
int k,n,len,i,j;
scanf("%d",&k);
while(k--){
scanf("%s",a);
len=strlen(a),j=1;
for(i=len-1;i>=0;i--)b[j++]=a[i]-'0';//逆序存储
b[0]=j-1;//b[0]存储数据长度
printf("%d\n",myPower(2011,10000));
}
return 0;
}
//1235 输出前k大的数
//快速排序
#include <stdio.h>
int a[100100];
void quicksort(int left,int right){//自大到小排序
int i=left,j=right,mid=a[(left+right)/2],t;
while(i<=j){
while(a[i]>mid)i++;
while(a[j]<mid)j--;
if(i<=j)t=a[i],a[i]=a[j],a[j]=t,i++,j--;
}
if(left<j)quicksort(left,j);
if(i<right)quicksort(i,right);
}
int main(){
int n,i,k;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
quicksort(1,n);
scanf("%d",&k);//漏了该句
for(i=1;i<=k;i++)printf("%d\n",a[i]);
return 0;
}
//1236 区间合并
//http://blog.****.net/qq_26140973/article/details/53453782此文写得真不赖,摘抄如下：
初看这题，感觉十分简单，就直接根据左端点排序后再一个一个判断能否满足条件，最后的答案就是数组中第一个区间的左端点和最后一个区间的右端点。 
但直接这样写，肯定是Wrong Answer了。然后发现：如果某一个区间的右端点十分靠右，那最终合并后的区间的右端点不应该是最右的那个吗？看来是答案出的问题。
结果还是错了。。。
再考虑一下极端情况，原来在先前的判断方法下有可能导致错误地出现no，给张图就明白了。 
应该与之前出现的最大的右端点作比较，而不是与上一个右端点作比较
//要用到相等时的快排，没办法，采用C++
//样例通过，提交AC 2017-12-12 21:35
#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
int left,right;
}d[50100];
int cmp(struct node a,struct node b){
return a.left<b.left||a.left==b.left&&a.right<b.right;//按左节点升序，若相等，按右节点升序
}
int main(){
int n,i,max_right=0;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d%d",&d[i].left,&d[i].right);
sort(d+1,d+1+n,cmp);
for(i=1;i<n;i++){
if(d[i].right>max_right)max_right=d[i].right;
if(d[i+1].left>max_right){
printf("no");
return 0;
}
}
if(d[i].right>max_right)max_right=d[i].right;
printf("%d %d",d[1].left,max_right);
return 0;
}
//1237 求排列的逆序数
//1311 【例2.5】求逆序对
//按冒泡思路编写，猜想，要超时，试试，看看数据水不水
//提交，果然超时，
//翻了之前的记录，发现是洛谷 P1908 逆序对 不过当时是用树状数组
//http://blog.****.net/mrcrack/article/details/61625530
//这次准备用归并排序做
//http://blog.****.net/yuehailin/article/details/68961304代码写得很对胃
//http://www.cnblogs.com/chengxiao/p/6194356.html用图分析归并排序算法过程，很清晰
//http://blog.****.net/acdreamers/article/details/16849761用归并排序求逆序对，关键点讲得好，摘抄如下：
//归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序，然后再将这两半合并起来。
//在合并的过程中（设l<=i<=mid，mid+1<=j<=h），当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在
//前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。因此，可以在归并
//排序中的合并过程中计算逆序数.
//样例通过，提交，未通过，
//同样的程序在洛谷里提交，AC，真是太奇葩了，洛谷 P1908 逆序对
//https://www.luogu.org/problemnew/show/P1908
//转念一想，可能是逆序对太多，int溢出，把int 改成long long 修改，提交AC 真不容易啊2017-10-28 22:26
//将int 改成 long long 整整用了17分钟
#include <stdio.h>
int a[100100],b[100100];
long long ans=0;////转念一想，可能是逆序对太多，int溢出，把int 改成long long
void memery_sort(int left,int mid,int right){//自小到大
int i=left,j=mid+1,n=mid,m=right,k=0;
while(i<=n&&j<=m)
if(a[i]>a[j]){
ans+=n-i+1;
b[k++]=a[j++];
}else
b[k++]=a[i++];
while(i<=n)b[k++]=a[i++];
while(j<=m)b[k++]=a[j++];
for(i=0;i<k;i++)a[left+i]=b[i];//1此处写成 for(i=1;i<k;i++)a[i]=b[i];
}
void merge_sort(int left,int right){
int mid=(left+right)/2;
if(left>=right)return ;
merge_sort(left,mid);
merge_sort(mid+1,right);
memery_sort(left,mid,right);
}
int main(){
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
merge_sort(0,n-1);
printf("%lld",ans);
return 0;
}
//1238 一元三次方程求解
//洛谷 P1024 一元三次方程求解
NOIP2001 提高组 复赛 一元三次方程求解
1.采用枚举的方式，因保留小数点后两位，故每次变量增加0.01
2.要注意浮点运算存在误差，故，相减<0.000001
3.按照题目要求编好程序，依次求出x1,x2,x3，没用到提示内容，觉得挺奇怪的。
4.样例通过后，提交AC，没觉得题目有什么特别，怎么会显示难度：普及/提高-
难度：简单
时间：20分钟
附上AC代码，编译环境Dev-C++4.9.9.2
//2001 fcqj
#include <stdio.h>
#include <math.h>
double a,b,c,d;
double f(double x){
int i;
double ans=0;
double y;
y=1;
for(i=1;i<=3;i++)
y*=x;
y*=a;
ans+=y;
y=1;
for(i=1;i<=2;i++)
y*=x;
y*=b;
ans+=y;
y=1;
y*=x;
y*=c;
ans+=y;
ans+=d;
return ans;
}
int main(){
double x,x1,x2,x3;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
x=-100;
while(x-100<=0.000001){
if(fabs(f(x))<=0.000001)
break;
x+=0.01;
}
x1=x;
x+=0.01;
while(x-100<=0.000001){
if(fabs(f(x))<=0.000001)
break;
x+=0.01;
}
x2=x;
x+=0.01;
while(x-100<=0.000001){
if(fabs(f(x))<0.000001)
break;
x+=0.01;
}
x3=x;
printf("%.2lf %.2lf %.2lf\n",x1,x2,x3);
}
//1239 统计数字
//快排，统计个数，输出
//样例通过，提交AC 2017-12-8
#include <stdio.h>
int a[200100],b[10100],c[10100];//b[]记录数，c[]记录数出现频率
void quicksort(int left,int right){
int i=left,j=right,mid=a[(left+right)/2],t;
while(i<=j){
while(a[i]<mid)i++;
while(a[j]>mid)j--;
if(i<=j){
t=a[i],a[i]=a[j],a[j]=t,i++,j--;
}
}
if(i<right)quicksort(i,right);
if(left<j)quicksort(left,j);
}
int main(){
int n,i,k;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
quicksort(1,n);
k=1,b[1]=a[1],c[1]=1;
for(i=2;i<=n;i++)
if(b[k]==a[i]){
c[k]++;
}else{
k++,b[k]=a[i],c[k]=1;
}
for(i=1;i<=k;i++)printf("%d %d\n",b[i],c[i]);
return 0;
}
//1240 查找最接近的元素
//样例通过，提交,10个测试点全部答案错误
//仔细想想，题意不清，非降序列，加入快排，提交，10个测试点全部答案错误
//考虑了各种情况，提交,10个测试点全部答案错误 2017-12-7 21:45
//http://www.oier.cc/noi1-11-01%E6%9F%A5%E6%89%BE%E6%9C%80%E6%8E%A5%E8%BF%91%E7%9A%84%E5%85%83%E7%B4%A0/此文代码写得够漂亮
//解题思路照抄如下：
//解题思路 非降序列，可以采用二分查找，这样每次查找的复杂度可以降到log级别。
//查找可能找到那个元素，也可能找不到，即使找不到，也要返回一个最接近的。
//因此，为了方便写代码，我们可以把他们合并在一起，即找最接近的2个元素，
//谁更接近就输出谁（如果找到的话，相等的更接近），这样可以避免很多细微的容易出错的地方。
//代码中，find函数退出循环时，l+1等于r，l是1或者a[l]比k小，
//r是n或者a[r]不比k小。如果k在a[1]和a[n]之间，那么a[l]<=k<=a[r]，否则k
//二分还是采用如下写法比较合适
//提交AC 2017-12-7 22:00
#include <stdio.h>
int a[100100];
int myabs(int x){
if(x>=0)return x;
else return -x;
}
int main(){
int n,m,i,q,left,right,mid;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
scanf("%d",&m);
while(m--){
scanf("%d",&q);
left=1,right=n;
while(left+1<right){//二分法
mid=(left+right)/2;//此处写成mid=(left+right);昏招
if(a[mid]<q)left=mid;
else right=mid;//此处写成 else if(a[mid]>q)right=mid;
}
if(myabs(q-a[right])<myabs(q-a[left]))printf("%d\n",a[right]);
else printf("%d\n",a[left]);
}
return 0;
}
//1241 二分法求函数的零点
//提交AC 2017-12-8
#include <stdio.h>
double f(double x){
return x*x*x*x*x-15*x*x*x*x+85*x*x*x-225*x*x+274*x-121;
}
double myabs(double x){
if(x<0)return -x;
return x;
}
int main(){
double left=1.5,right=2.4,mid;
while(left+0.0000001<right){
mid=(left+right)/2;
if(f(mid)>0)left=mid;//此处写成 if(f(mid)<0)left=mid;请注意，减函数
else right=mid;
}
if(myabs(f(left))>myabs(f(left+0.0000001)))printf("%.6lf",left+0.0000001);
else printf("%.6lf",left);
return 0;
}
//1242 网线主管
//网络上搜索一通，大部分代码，测试点4答案错误
//http://blog.****.net/ascvsderf/article/details/49560455此文代码AC
//http://blog.****.net/Darost/article/details/51548271此文代码AC
//http://blog.****.net/qq_37657307/article/details/72582030此文代码AC
//样例通过，提交，测试点4,7,8答案错误，
//right+=1;//添加此句，只有测试点4 答案错误
//a[i]=(int)(b*100+0.5);//a[i]=(int)(b*100);测试点4 答案错误
//经历上述修改，测试点4 答案错误，
//样例通过，提交AC 2017-12-11
#include <stdio.h>
int n,k,a[10100];
int judge(int x){
int i,ans=0;
for(i=1;i<=n;i++)
ans+=a[i]/x;
return ans>=k;
}
int main(){
int i,j,left=0,right=0,mid;
double b;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++){
scanf("%lf",&b),a[i]=(int)(b*100+0.5);//注意，读取双精度浮点时，存在误差，故要+0.5 4.00存储为3.9999...//a[i]=(int)(b*100);测试点4 答案错误
if(right<a[i])right=a[i];
}
right+=1;//注意一定要加1，如果出现l=200，r=201这样的情况不加1就会卡掉//添加此句，只有测试点4 答案错误
while(left+1<right){
mid=(left+right)/2;
if(judge(mid))left=mid;
else right=mid;
}
printf("%.2lf",left/100.0);
return 0;
}
//1243 月度开销
//没想到该题是用二分处理的
//http://blog.****.net/darost/article/details/51542708此文代码写得很对胃,思路摘抄如下
//本题把总和当做r, 然后check, 即连续几个数的和<mid就可以分一组, 分完一组count++, 最后比较count和m即可
//注意判断一个月与mid的关系, 有可能一个月已经超过了mid, 出现这种情况, 直接修改l即可
//http://blog.****.net/xhk2000/article/details/52347203此文也可作参考
//此种类型的二分法，难在判断函数的编写
//体会，此种类型问题，要做专门训练，掌握判断函数编写是关键
//总结，此类型问题，掌握不好。2017-12-10 16:07
//样例通过，提交AC
#include <stdio.h>
int n,m,a[100100];
int judge(int x){//在此类题型中，该函数编写最难
int b=0,c=0,d,i;
for(i=1;i<=n;i++){
b+=a[i];
if(b>=x){
c++;
if(a[i]<x)b=a[i];//可以考虑让上一个周期为...+a[i-1]
else return 1;//a[i]>=x左边界left=mid;
}
}
return c>=m;//存在最后的元素之和 b<x，该组周期未统计进c中，故实际分组为c+1组，故此处写成c+1>m合理，等价于c>=m.c>=m表明分组过多，即左边界left=mid
}
int main(){
int i,left,right,mid,tot=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]),tot+=a[i];
left=1,right=tot;
while(left+1<right){
mid=(left+right)/2;
if(judge(mid))left=mid;
else right=mid;
}
if(judge(left))printf("%d",left);
else printf("%d",right);
return 0;
}
//1244 和为给定数
//https://www.cnblogs.com/geek-007/p/5667447.html瞄了一眼文中代码，开始编码
//样例通过，提交AC，下面代码，为适应面比较广的二分代码，2017-12-8
#include <stdio.h>
int a[100100];
void quicksort(int left,int right){//自小到大排序
int i=left,j=right,mid=a[(left+right)/2],t;
while(i<=j){
while(a[i]<mid)i++;
while(a[j]>mid)j--;
if(i<=j){
t=a[i],a[i]=a[j],a[j]=t,i++,j--;
}
}
if(i<right)quicksort(i,right);
if(left<j)quicksort(left,j);
}
int main(){
int n,i,j,left,right,m,p,mid;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
quicksort(1,n);
scanf("%d",&m);
for(i=1;i<n;i++){
p=m-a[i],left=i+1,right=n;
while(left+1<right){
mid=(left+right)/2;
if(a[mid]<p)left=mid;
else right=mid;
}
if(a[left]==p||a[right]==p){
printf("%d %d",a[i],p);
return 0;
}
}
printf("No");
return 0;
}
//1245 不重复地输出数
//快排，不重复输出
//样例通过，提交AC 2017-12-7 20:35
#include <stdio.h>
int a[100100];
void quicksort(int left,int right){
int i=left,j=right,mid=a[(left+right)/2],t;
while(i<=j){
while(a[i]<mid)i++;
while(a[j]>mid)j--;
if(i<=j){
t=a[i],a[i]=a[j],a[j]=t,i++,j--;
}
}
if(i<right)quicksort(i,right);
if(left<j)quicksort(left,j);
}
int main(){
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
quicksort(1,n);
printf("%d",a[1]);
for(i=2;i<=n;i++)
if(a[i]!=a[i-1])printf(" %d",a[i]);
return 0;
}
//1246 膨胀的木棍
//网络中的答案，均是测试点1-2,6-10 答案错误
//基本确认，该题的测试点数据 全是用特殊的方法 求得的，对于浮点数，一题多解 不适合
//翻看《信息学奥赛一本通(C++版)》特殊思路：用不同的方法算出 弦长/2，用二分法缩小差距
//样例通过，提交，测试点2,4答案错误，一看是精度问题 left+1e-6<right，改成 left+1e-8<right发现能AC
//此题用枚举的方式，估计无法AC。2017-12-12 20:43
#include <stdio.h>
#include <math.h>
int main(){
double L,N,C,left,right,mid,S;
scanf("%lf%lf%lf",&L,&C,&N);
S=(1+N*C)*L,left=0,right=acos(-1.0);//反三角 cos(PI)=-1
while(left+1e-8<right){
mid=(left+right)/2;
if(S/mid*sin(mid/2)>=L/2)left=mid;//sin(mid/2)/mid是单调减函数,S/mid是半径
else right=mid;
}
printf("%.3lf",S/left*(1-cos(mid/2))); //S/left是半径
return 0;
}
//1247 河中跳房子
//http://blog.****.net/mrcrack/article/details/79249249可以参考该文
//3135 River Hopscotch
//二分法是肯定的，因1<=L<=1000000000
//根据距离移走石头，移走石头个数过多，距离过大 right=mid ,移走石头个数过少或刚好，距离过小或刚好 left=mid
//此种二分，难在 判断 函数 的编写
//从样例来看，石头离按距离，需要排序，采用快排
//样例通过，提交 测试点3,4 WA ,对于codevs网站满意之处，在于,看到了第一个错误的测试点 数据
//
//3135 River Hopscotch
//测试数据
//输入:
//250 8 4
//3
//45
//32
//12
//56
//89
//203
//109
//输出：
//24
//上述样例思考过程如下图：
//上述数据通过，样例通过，提交AC 2018-2-8 22:55
//http://ybt.ssoier.cn:8088/problem_show.php?pid=1247中提交，同样AC 河中跳房子
//此中题目的难点在于，cnt==m时，是left=mid还是right=mid，读者还是要多模拟，笔者有更多经验时，争取将此类问题说清。
#include <stdio.h>
int L,n,m,d[50100];
void quicksort(int left,int right){//快排，自小到大
int i=left,j=right,mid=d[(left+right)/2],t;
while(i<=j){
while(d[i]<mid)i++;
while(d[j]>mid)j--;
if(i<=j)t=d[i],d[i]=d[j],d[j]=t,i++,j--;
}
if(left<j)quicksort(left,j);
if(i<right)quicksort(i,right);
}
int judge(int x){//移走石头个数过多，距离过大 right=mid 返回值为1 ,移走石头个数过少或刚好，距离过小或刚好 left=mid 返回值为0
int pre,i,cnt;
pre=0,i=pre+1,cnt=0;//下面代码，边界处理花了很长时间，思考时间跨度超过一天，不过思维确实得到很好的锻炼
while(i<=n){//此处写成 while(i<=n+1)
while(i<=n&&d[i]-d[pre]<x)i++,cnt++;//此处写成 while(i<=n+1&&d[i]-d[pre]<x)i++,cnt++;
if(i<=n)pre=i,i=pre+1;//此处写成 if(i<=n+1)pre=i,i=pre+1;
}
//printf("x=%d cnt=%d m=%d d[%d]=%d\n",x,cnt,m,pre,d[pre]);
if(d[n+1]-d[pre]<x)cnt++;//最后一块石头要单独判定,若 d[n+1]-d[pre]<x 移走d[pre]这块石头
if(cnt>m)return 1;//此处写成if(cnt>=m)return 1;//因是求最小距离，故将等号放于 right=mid这一侧 后发现错误
else return 0;
}
int main(){
int i,left,right,mid;
scanf("%d%d%d",&L,&n,&m);
for(i=1;i<=n;i++)scanf("%d",&d[i]);
quicksort(1,n),d[0]=0,d[n+1]=L;
left=1,right=L;
while(left+1<right){
mid=(left+right)/2;
//printf("%d %d\n",judge(mid),mid);
if(judge(mid))right=mid;
else left=mid;
}
printf("%d",left);//此处写成 printf("%d",right);
return 0;
}
//1247 河中跳房子
//1 ≤ L≤ 1,000,000,000该题要与二分联系，但怎么联系，却犯愁了。
//https://www.cnblogs.com/KakagouLT/p/5001800.html代码写得不错,思路摘抄如下：
//这题二分的思路是这样的：
//先存好全部石头数据
//然后用二分取一个最长的最短跳跃距离，即mid
//当选出一对石头j与i，它们之间的距离>=mid，就把它们中间的石头算作移除，移除数量就是j-i-1
//移除之后，从石头j开始，继续往后算，除非算到了n+1，自然就不能继续算下去了
//算完之后，用总移除数ans对比实际可以移除的石头数m
// 当ans<m，说明取的mid间距太短，导致某些石头间的距离大于mid时无法移除石头，所以l=mid
// 当ans==m，别急，也许某些石块移除后，两块石头的距离比mid大，说明mid可能还是小了，所以l=mid
// 当ans>m，说明取的mid太长，导致本来对某对石头进行移除操作就合适的时候还继续往下找，所以r=mid
//最后l==r，输出l
//可以举一个极端的例子说明ans与m的比较
//假设石头是这样的：
//0 20 23 26 29 31 51 (r=52)
//只允许移除3块石头。这样的情况下自然是移除中间3块石头，不然最短距离将会是3或是6。
//设mid为（0+52）/2=26，则会移除20、23两块石头，再移除29、31两块石头，ans>m，r=mid=26
//mid=(0+26)/2=13，则20与0空移除一次，再移除23、26、29、31，同理r=mid=13
//mid=(0+13)/2=6，则先空移除，然后移除23，移除29，31与51空移除，ans<m，l=mid=6
//mid=(6+13)/2=9，移除23、26、31。ans==m了，就行了吗？不，明显20与29距离是9，还可以更长为11，那就加长试试，l=9
//mid=(9+13)/2=11，移除23、26、29。此时还不能确定11就是最优解，因为还有12，所以l=11
//mid=12，移除了23、26、29、31，所以r=12
//mid=11，又区间是[l,r)左闭右开型的，即现在能确定距离就是mid=l=11了。
//Ps 做了这么多二分，果然中值赋值条件是难点所在啊！
//http://www.oier.cc/noi1-11-10%e6%b2%b3%e4%b8%ad%e8%b7%b3%e6%88%bf%e5%ad%90%ef%bc%88noip2015%e8%b7%b3%e7%9f%b3%e5%a4%b4%ef%bc%89/此文代码写得真不错,思路摘抄如下：
//题目的答案范围已知，而且范围很大，对于每个答案可以快速验证是否可行，可以采用二分答案的方法。
//最短距离最大，其实就是越大越好——在二分的时候，如果中间值可行，继续猜后一半，而不是前一半，
//因为后一半可能有更好的！对于一个答案m，如果可行，那么相邻石头之间的距离都不小于m，
//也就是如果出现小于m的，那个石头必须移走。写一个函数判断当前答案需要移走多少块石头，如果不超过k块，
//那就可以，否则不行。
//样例通过，提交AC 2017-12-10 20:17
#include <stdio.h>
int L,n,m;
int a[50100];
int judge(int x){
int i,p=0,c=0;
for(i=1;i<=n;i++)
if(a[i]-p<x)c++;//移走a[i],p值不变
else p=a[i];//a[i]>=p，故a[i]保留，作为新的p
if(L-p<x)c++;//因L处石头无法移走，故将p移走
return c<=m;//移走不超过m块即可//此处写成 return c<=x;尽出昏招
}
int main(){
int i,left,right,mid;
scanf("%d%d%d",&L,&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
left=0,right=L;
while(left+1<right){
mid=(left+right)/2;
if(judge(mid))left=mid;//left有可能可行
else right=mid;//right永远不可行
}
printf("%d",left);
return 0;
}
2018-1-15 AC 该章节内容