数形结合、单调队列+uva1451

解题思路:

     1. 这题是一道数形结合的问题, 我从《浅谈数形结合思想在信息学竞赛中的应用》学习而得算法.

     设Sum[i] = a1+a2+...+ai,那么平均值ave(i,j) =(sum[j]-sum[i-1])/(j-(i-1));

     容易发现问题可以转换为:求函数function(i,Sum[i])的任意两点的最大斜率.具体可以从学习

     上面提到的《浅谈数形结合思想在信息学竞赛中的应用》讲解, 我只提出一点就是:维护下凸曲线

      例如: 明显斜率K(j,i)>K(k,j),K(i,k)

      无法确定更大的斜率K,j点可以说是多余的,因此要维护下凸曲线(斜率逐渐变大的曲线).

      2. 题目到这里其实可以做了,用单调队列就可以了.

   这相当于一个非递减数列，i是x坐标，sum[i]是y坐标，在这个图上找y-x>=L的斜率最大的两个点。用一个队列保存当前可能用到的起点，设i从L递增到N，我们每次在队列中加入i-L作为起点，设rear为当前队列中最后一个元素。如果发现rear和i-L这两个点的斜率小于等于rear-1和rear这两个点的斜率，也就是rear-1,rear,i-L三个点一次连成的曲线不是下凸的，就可以把rear这个点删掉了。这是因为后面再出现的点怎么都不可能和rear这个点构成最大斜率（可以自己画个图看一下）。从后删到不能删后，把i-L加到最后。不光可以从后删掉一些没用的点，还可以从前删掉一些。如果front那个点和i点的斜率小于front+1和i的斜率，那么front这个点可以删掉，因为y是单调不减的，后面再出现的点如果可能更新最大斜率的话，明显和front+1构成的斜率更优。这样又从前删掉了一些点。删完后i和当前的front就是i点作为end的最优答案。

  总之，队列中的点都是当前有可能作为起点的，是一条下凸曲线。这样就比遍历一遍省时间，省去了一些没用的点。

#include
#include
#include
#include
#include
using namespace std;
const int maxn=100005;
int len,l;
char s[maxn];
int sum[maxn],q[maxn];
double k(int x,int y)
{return (sum[y]-sum[x])*1.0/(y-x);
}
int main()
{//freopen("in.txt","r",stdin);int t;scanf("%d",&t);while(t--){scanf("%d%d%s",&len,&l,s);int n=strlen(s);sum[0]=0;for(int i=1;i<=n;i++)sum[i]=sum[i-1]+s[i-1]-'0';int front=0,rear=-1;double ans=0;int anslen=0,x=0,y=l;for(int i=l;i<=n;i++){int tmp=i-l;while(frontans){ans=m;anslen=tmplen;x=q[front],y=i;}}printf("%d %d\n",x+1,y);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！