玲珑OJ1088【蜜汁尺取】

前言（膜法）：

早上10点多开始膜的，然后到中午交了一发，感觉膜法不对啊！然后就兴起小窗了一发管理员，然后管理员给我发了in，out数据。。。可是太大并没有什么可取性。。。

还是自己试，然后发现自己搞的案例都过，后面放着不玩了，然后队友给了我一题以前做过的dfs写，然后写了以后T了，后面我就跟他讲这道题。。。讲完好我说我的方法，他硬是不懂我的尺取，然后搞了一个破案例我模拟发现，卧槽我左指针移的时候发现，区间突然没有取前m最大惹，后面在左指针移的时候改了一下，gg，wa的。然后继续测，继续wa。然后发现噢噢噢噢，那样子搞的！始终都要前m大，然后就这样了，膜了一发过了。。。破水题，坑了一天，不过事后发现以后做题要对重要条件特别照顾，始终照顾。然后CF也没打。。。万事大吉，然后就和女朋友去散步了。

题意：

先选一段连续的区间，能够免费m个，免费是任意位置，求一个获得价值最大；

思路：

重点就是在于怎么搞出一个区间的前m大，而且是始终都要。

尺取，对区间里的数进行分类，一类是免费，一类是付钱，那我肯定是免费最贵的，因为最终我的钱多呀！

然后具体操作是两个优先队列搞的，一个队列是付钱的最大，一个队列是免费的最小，这样维护复杂度还好吧。

//#include <bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<queue>

#include<string.h>

#include<algorithm>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

const int N=1e5+10;

struct asd{

    int id,w;

    friend bool operator< (asd n1,asd n2)

	{

        if(n1.w==n2.w) return n1.id>n2.id;

        return n1.w>n2.w;

    }

};

struct dsa{

    int id,w;

	friend bool operator< (dsa n1,dsa n2)

	{

        if(n1.w==n2.w) return n1.id>n2.id;

        return n1.w<n2.w;

	}

};

int a[N],b[N],sum[N];

bool vis[N];

priority_queue<asd>q;	//区间内免费的物品

priority_queue<dsa>p;	//区间内花费的物品

int cost,val,out;

dsa have(int s)

{

	dsa now;

	while(!p.empty())

	{

		if(p.top().id<s)

			p.pop();

		else

			break;

	}

	if(!p.empty())

	{

		now=p.top();

		return now;

	}

	now.id=0;

	return now;

}

asd get_q(int s)

{

	while(!q.empty())

		if(q.top().id<s)

		{

			q.pop();

			out--;

		}

		else

			break;

	asd now;

	now=q.top();

	return now;

}

int main()

{

    int T,n,m,k;

    scanf("%d",&T);

    while(T--)

    {

        while(!q.empty())

			q.pop();

		while(!p.empty())

			p.pop();

        scanf("%d%d%d",&n,&m,&k);

        for(int i=1;i<=n;i++)

            scanf("%d",&a[i]);

        sum[0]=0;

        for(int i=1;i<=n;i++)

		{

            scanf("%d",&b[i]);

            sum[i]=sum[i-1]+b[i];

            vis[i]=false;

        }

        asd now,nex;

        dsa nnn,mmm;

        int s,t;

        out=0;	//out代表，在队列里的实际已经出队的元素个数

        cost=0;	//代表花费。

        val=0;	//代表得的价值。

		s=t=1;

		while(s<=n)

		{

			while(t<=n)

			{

				if((q.size()-out)<m)

				{

					nnn.id=t;nnn.w=a[t];p.push(nnn);

					cost+=nnn.w;

					mmm=have(s);

					cost-=mmm.w;

					now.id=mmm.id;now.w=mmm.w;

					vis[now.id]=1;

					p.pop();

					q.push(now);

					val=max(val,sum[t]-sum[s-1]);

					t++;

				}

				else if((q.size()-out)==m)

				{

					now=get_q(s);

					if(cost+a[t]>k&&cost+now.w>k)

						break; 

					nnn.id=t;nnn.w=a[t];p.push(nnn);

					cost+=a[t];

					mmm=have(s);

					if(mmm.w>now.w)

					{

						cost-=mmm.w;

						cost+=now.w;

						q.pop();

						p.pop();

						nnn.id=now.id;nnn.w=now.w;

						vis[nnn.id]=0;

						p.push(nnn);

						nex.id=mmm.id;nex.w=mmm.w;

						vis[nex.id]=1;

						q.push(nex);

					}

					val=max(val,sum[t]-sum[s-1]);

					t++;

				}

				else break;

			}

			//printf("%d %d\n",s,t);

			//printf("%d\n",val);

			if(vis[s])

			{

				vis[s]=false;

				out++;

			}

			else

				cost-=a[s];

			s++;

		}

        printf("%d\n",val);

    }

    return 0;

}

/*

100

6 1 4

5 3 2 4 1 6

2 4 3 1 6 5

5 1 6

1 2 5 4 3

2 2 5 4 8

5 2 6

1 2 5 4 3

2 2 5 4 8

6 2 4

5 3 2 4 1 6

2 4 3 1 6 5

6 2 4

1 7 1 7 1 6

2 4 3 1 6 3

6 2 4

1 7 1 7 1 6

2 4 3 1 6 3

5 2 2

1 2 5 4 3

2 2 5 4 8

5 1 1

8 5 4 3 2

1 2 3 4 5

4 1 3

4 2 2 3

3 2 4 5

*/

巴特西

玲珑OJ1088【蜜汁尺取】

最新文章

热门文章