本文主要是介绍组队赛第六场：贪心+RMQ加二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
UVALive 6606 Meeting Room Arrangement
COJ有这题，一模一样的，COJ应该是从这个OJ上拿的吧。
按右端点排序，然后从第一个开始贪心的取相邻的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
#define maxn 40
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct abc
{int l,r;bool operator<(const abc &b)const{return r<b.r;}
}a[22];
int main()
{//freopen("1.txt","r",stdin);int n;scanf("%d",&n);while(n--){int i,j,l,r,sum=1;for(i=0;;i++){scanf("%d%d",&l,&r);if(l==0&&r==0) break;a[i].l=l,a[i].r=r;}sort(a,a+i);l=a[0].r;for(j=1;j<i;j++)if(a[j].l>=l) sum++,l=a[j].r;printf("%d\n",sum);}return 0;
}UVALive 6609 Minimal Subarray Length
思路：RMQ+二分
把递推和用RMQ先预处理一下区间最大值，然后枚举下标 i，然后二分查找 i 后面>=x位置的最小值，其差就是区间。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
#define maxn 500050
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll a[maxn],dp[maxn][34];
void RMQ(int n)
{int i,j;for(i=1;i<=n;i++)dp[i][0]=a[i];for(j=1;(1<<j)<=n;j++)for(i=1;i+(1<<j)-1<=n;i++)dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
ll rmq(int l,int r)
{int k=log2(r-l+1.0);return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main()
{//freopen("1.txt","r",stdin);int t;scanf("%d",&t);while(t--){int n,x,i,ans;scanf("%d%d",&n,&x);for(i=1;i<=n;i++)scanf("%lld",a+i),a[i]=a[i]+a[i-1];RMQ(n);for(i=0,ans=INF;i<n;i++){int l=i+1,r=n,mid;while(l<r){mid=(l+r)>>1;if(rmq(i+1,mid)-a[i]>=x) r=mid;else l=mid+1;}if(a[r]-a[i]>=x) ans=min(ans,r-i);}if(ans==INF) puts("-1");else printf("%d\n",ans);}return 0;
}
UVALive 6604 Airport Sort
思路：由k对数进行分组，然后用归并求出最小的交换次数。然后先求出第二种的最大的移动时间。它们之差就是答案。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffffffffffff
#define maxn 20050
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll sum;
void merge(ll A[], int p, int q, int r)
{int n1 = q - p + 1;int n2 = r - q;ll *L=new ll[n1 + 1];ll *R=new ll[n2 + 1];for(int i = 0; i < n1; i++)L[i] = A[p + i];for(int i = 0; i < n2; i++)R[i] = A[q + 1 + i];L[n1] = INF;R[n2] = INF;int i = 0, j = 0;for(int k = p; k <= r; k++){if(L[i] <= R[j]) A[k] = L[i],i++;else A[k] = R[j],j++,sum += n1 - i;}delete []L;delete []R;
}
void mergesort(ll A[], int l, int r)
{if(l >= r) return ;int q = (l + r) / 2;mergesort(A, l, q);mergesort(A, q + 1, r);merge(A, l, q, r);
}
ll a[maxn];
int main()
{//freopen("1.txt","r",stdin);int t,ii=1;scanf("%d",&t);while(t--){int n,k,i;ll ans=0;sum=0;scanf("%d%d",&n,&k);for(i=1;i<=n;i++){scanf("%d",a+i),a[i]=(a[i]-1)/k+1;int mm=(i-1)/k+1;if(mm>a[i])ans=max(ans,i-k*a[i]);else if(mm<a[i])ans=max(ans,k*(a[i]-1)-i+1);}mergesort(a,1,n);printf("Case %d: %lld\n",ii++,sum-ans);}return 0;
}
这篇关于组队赛第六场：贪心+RMQ加二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
