下面的题目都还是挺不错的，因为比较简单，所以说就不写题解了，有疑问的可以去看题目的题解，这里只放代码：
一道最长不下降子序列的题目（二分优化）
/*
Name:【P1233】木棍加工
Copyright: njc
Author: Mudrobot
Date: 2018/10/12 15:29:47
Description: greedy！
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 20000
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
struct sd{int x,y;}stk[N];
int n,mp[N];
bool cmp(sd a,sd b){if(a.x>b.x) return true;if(a.x==b.x&&a.y>b.y)return true;return false;}
int main()
{
read(n);
for(int i=1;i<=n;++i) read(stk[i].x),read(stk[i].y);//scanf("%d%d",&stk[i].x,&stk[i].y);
sort(stk+1,stk+1+n,cmp); int ans=0;
for(int i=1;i<=n;++i)
{
if(stk[i].y>mp[ans])mp[++ans]=stk[i].y;
else
{
int l=1,r=ans;
while(l<=r)
{
int mid=(l+r)/2;
if(mp[mid]>=stk[i].y)r=mid-1;
else l=mid+1;
}
mp[l]=stk[i].y;
}
}
printf("%d",ans);
return 0;
}
/*
*/
二分好题，注意取斜率小于0的最右边和斜率大于0的左边进行二分！（差为0时就是我们要找的答案点）
/*
Name: P1663 山
Copyright: njc
Author: Mudrobot
Date: 2018/10/20 15:39:54
Description: Binary Search
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 5005
#define INF 1000004
#define eps 0.01
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
struct sd{
double k,b;
}line[N];
int n,x[N],y[N];
void construct(int a1,int a2){
double x1=(double)x[a1],y1=(double)y[a1],x2=(double)x[a2],y2=(double)y[a2];
line[a1].k=(y1-y2)/(x1-x2);line[a1].b=y1-line[a1].k*x1;
}
bool check(double y){
bool flag1=false,flag2=false;
double right=0,left=0;
for(int i=1;i<n;++i){
if(fabs(line[i].k)==0&&line[i].b>y) return false;
if(line[i].k<0){
if(!flag1){flag1=true;right=(y-line[i].b)/line[i].k;}
else right=max(right,(y-line[i].b)/line[i].k);
}
else if(line[i].k>0){
if(!flag2){flag2=true;left=((y-line[i].b)/line[i].k);}
else left=min(left,(y-line[i].b)/line[i].k);
}
}
if(left-right>=0) return true;
return false;
}
int main()
{
//freopen(".in", "r", stdin);freopen(".out", "w", stdout);
read(n);
for(int i=1;i<=n;++i) read(x[i]),read(y[i]);
for(int i=2;i<=n;++i) construct(i-1,i);
//for(int i=1;i<n;++i) printf("%lf %lf
",line[i].k,line[i].b);
double l=0,r=INF,final;
while(r-l>=eps){
double mid=(l+r)/2;
if(check(mid)) final=mid,r=mid;
else l=mid;
}
printf("%.2lf",final);
//fclose(stdin);fclose(stdout);
return 0;
}
/*
6
0 0
10 0
11 1
15 1
16 0
25 0
*/
模板题，不多说！先做映射，然后求下一个序列的最长不下降子序列！
/*
Name: P1439 【模板】最长公共子序列
Copyright: njc
Author: Mudrobot
Date: 2018/10/20 16:29:47
Description: greedy!+Binary Search
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 200000
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
struct sd{int x,y;}stk[N];
int n,mp[N],nas[N],ma[N];
bool cmp(sd a,sd b){if(a.x>b.x) return true;if(a.x==b.x&&a.y>b.y)return true;return false;}
int main()
{
read(n);
for(int i=1;i<=n;++i) read(stk[i].x),ma[stk[i].x]=i;
for(int i=1;i<=n;++i) read(stk[i].y);//scanf("%d%d",&stk[i].x,&stk[i].y);
for(int i=1;i<=n;++i) stk[i].y=ma[stk[i].y];
int ans=0;
for(int i=1;i<=n;++i)
{
if(stk[i].y>mp[ans])mp[++ans]=stk[i].y,nas[ans]++;
else
{
int l=1,r=ans;
while(l<=r)
{
int mid=(l+r)/2;
if(mp[mid]>=stk[i].y)r=mid-1;
else l=mid+1;
}
mp[l]=stk[i].y;nas[l]++;
}
}
int ns=0;
for(int i=1;i<=ans;++i) ns=max(ns,nas[i]);
printf("%d",max(ns,ans));
return 0;
}
/*
5
3 2 1 4 5
1 2 3 4 5
*/
注意 long double ！！！
/*
Name: P1542 包裹快递
Copyright: njc
Author: Mudrobot
Date: 2018/10/20 16:50:06
Description: Binary Search
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 200005
#define eps 0.000000001
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
struct sd{
double len,s,e;
}p[N];
int n;
bool check(long double v){
long double tim=0;
for(int i=1;i<=n;++i){
tim+=(long double)p[i].len/v;
//if(tim>(long double)p[i].s&&tim<(long double)p[i].e) continue;
if(tim>(long double)p[i].e) return false;
if(tim<(long double)(p[i].s))tim=p[i].s;
}
return true;
}
int main()
{
//freopen(".in", "r", stdin);freopen(".out", "w", stdout);
read(n);
for(int i=1;i<=n;++i) scanf("%lf%lf%lf",&p[i].s,&p[i].e,&p[i].len);
long double l=0.0000000,r=0x7fffffff;
long double final;
while(r-l>=eps){
long double mid=(l+r)/2.00;
if(check(mid)) final=mid,r=mid;
else l=mid;
}
printf("%.2lf",(double)final);
//fclose(stdin);fclose(stdout);
return 0;
}
/*
3
1 2 2
6 6 2
7 8 4
*/
#include<cstdio>
#include<cstring>
using namespace std;
double a,b,c,d;
double njc(double x)
{
return (a*x*x*x+b*x*x+c*x+d);
}
int main()
{
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
double p1,p2,tt;
for(int i=-100;i<=100;++i)
{
p1=i; p2=i+1;
if(njc(p1)==0) printf("%.2lf ",p1);
else if(njc(p1)*njc(p2)<0)
{
while(p2-p1>=0.001)
{
tt=(p2+p1)/2;
if(njc(p1)*njc(tt)<=0)
{
p2=tt;
}
else p1=tt;
}
printf("%.2lf ",p2);
}
}
}
/*
Name: P1316 丢瓶盖
Copyright: njc
Author: Mudrobot
Date: 2018/10/16 20:33:24
Description: Binary_Search
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 100005
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
int n,k,a[N],minn=N*100,maxx=0;
bool check(int kk){
int cnt=1,s=1;
for(int i=1;i<=n;++i){
if(a[i]-a[s]<kk) continue;
s=i;cnt++;
}
if(cnt>=k) return true;
return false;
}
int main()
{
//freopen(".in", "r", stdin);freopen(".out", "w", stdout);
read(n);read(k);
for(int i=1;i<=n;++i) read(a[i]),maxx=max(maxx,a[i]),minn=min(minn,a[i]);
sort(a+1,a+1+n);
int l=1,r=maxx,ans;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d",ans);
//fclose(stdin);fclose(stdout);
return 0;
}
/*
5 3
1 2 3 4 5
*/
/*
Name: P2370 yyy2015c01的U盘
Copyright: njc
Author: Mudrobot
Date: 2018/10/17 21:05:24
Description: Binary_Search
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 1005
using namespace std;
/*inline char gc() {
static char buf[1<<18],*fs,*ft;
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
register int k=0,f=1;
register char c=gc();
for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
struct sd{
int w,val;
}doc[N];
int n,p,s,bag[N],maxx;
bool check(int lim){//最大文件的大小
memset(bag,0,sizeof(bag));
for(int i=1;i<=n;++i){
if(doc[i].w>lim) continue;
for(int j=s;j>=0;--j){
if((j==0||bag[j])&&j+doc[i].w<=s){
bag[j+doc[i].w]=max(bag[j+doc[i].w],bag[j]+doc[i].val);
}
}
}
int ans=0;
for(int i=1;i<=s;++i) ans=max(ans,bag[i]);
return ans>=p;
}
int main()
{
//freopen(".in", "r", stdin);freopen(".out", "w", stdout);
read(n);read(p);read(s);//p是我们希望的价值
for(int i=1;i<=n;++i){
read(doc[i].w);read(doc[i].val);
maxx=max(maxx,doc[i].w);
}
int l=1,r=maxx;
int ans;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
if(check(r))printf("%d",l);
else printf("No Solution!");
//fclose(stdin);fclose(stdout);
return 0;
}
/*
4 5 6
5 1
5 2
5 3
1 1
*/
#include<bits/stdc++.h>
using namespace std;
int l,m,n;
int len[50005],dis[50005];
int minx=1000000;
int search(int mid)
{
int cnt=0;
for(int i=0;i<=n;++i)
{
int p=1;
while(len[i+p]-len[i]<mid&&i+p<=n)
{p++;cnt++;}
i=i+p-1;
}
return cnt;
}
int main()
{
len[0]=0;
scanf("%d%d%d",&l,&n,&m );
if(m==0) {printf("%d",l);exit(0);}
for(int i=1;i<=n;++i)
{
scanf("%d",&len[i]);
if(minx>len[i]) minx=len[i];
dis[i-1]=len[i]-len[i-1];
}
len[n+1]=l;
dis[n]=len[n+1]-len[n];
int p1,p2;
p1=0;p2=len[n];
int mid;
int ans;
while(p1<=p2)
{
mid=(p1+p2)/2;
int goal=search(mid);
if(goal<=m){p1=mid+1;ans=mid;}
if(goal>m){p2=mid-1;}
}
printf("%d",ans);
return 0;
}
/*
Name: P1404 平均数
Copyright: njc
Author: Mudrobot
Date: 2018/10/22 14:29:08
Description: Binary Search
*/
#include<bits/stdc++.h>
#define N 100005
typedef long long ll;
using namespace std;
ll n,m,s[N];
double ans=0.0;
ll q[N],t,h; // 队列
double k(ll x,ll y){ // 计算s[x],s[y]的斜率
return (s[y]-s[x]+0.0)/(y-x);
}
int main() {
cin>>n>>m;
for (ll i=1,x;i<=n;i++){
cin>>x; s[i]=s[i-1]+x;
}
for (ll i=m;i<=n;i++){
while (t-h>=2 && k(i-m,q[t-1])<k(i-m,q[t-2])) t--; // 删除上凸点
q[t++]=i-m; // 入队
while (t-h>=2 && k(i,q[h])<k(i,q[h+1])) h++; // 移动最大斜率点
ans=max(ans,k(i,q[h]));
}
cout<<(ll)floor(ans*1000)<<endl;
return 0;
}
/*
10 6
6
4
2
10
3
8
5
9
4
1
*/
(↑↑↑贼卡精度！↑↑↑)