为什么总有两个样例过不了啊,求教大佬
查看原帖
为什么总有两个样例过不了啊,求教大佬
524450
yiduiiii楼主2023/9/30 23:38
#include <iostream>
#include <cstdio>
#include <deque>
#include <algorithm>
#define inf 0x0f0f0f0f
using namespace std;
long long int l;
int s, t, m;

int main()
{
	//freopen("P1052.in", "r", stdin);
	//freopen("P1052.out", "w", stdout);

   //输入 初始化
	cin >> l;
	cin >> s >> t >> m;
	long long int stoneidx[m+2], nsi[m+1];//stoneidx石头初始位置 nsi压缩后的位置
	stoneidx[0]=0, nsi[0]=0;
	for (int i=1; i<=m; i++)
	{
		cin >> stoneidx[i];
	}
   stoneidx[m+1]=l;
	sort(stoneidx+1, stoneidx+m+1);

   //测试的,不用管
	//for (int i=1; i<=m; i++) cout << stoneidx[i] << ' ';
	//cout << endl;

   //路径压缩
	for (int i=1; i<=m+1; i++)
	{
		if (stoneidx[i]-stoneidx[i-1]>s+t)
		{
			l=l-stoneidx[i]+stoneidx[i-1]+s+t;
			nsi[i]=nsi[i-1]+s+t;
		}
		else if (i!=m+1)
		{
			nsi[i]=stoneidx[i]-stoneidx[i-1]+nsi[i-1];
		}

      //测试用的
		//cout << l << endl;


	}



   //测试用的
   //for (int i=1; i<=m; i++) cout << nsi[i] << ' ';
   //cout << endl;
	//cout << l << endl;

   //标记石头位置
	int brd[l+t]={0};//brd[]桥的dp数组
	for (int i=1; i<=m; i++) brd[nsi[i]]=1;
	
   //dp
	deque<int> dq;//dq 用来做dp优化的双端队列
	int cur=0;//cur 目前入队的位置
	for (int i=1; i<l; i++)
	{
		while (!dq.empty()&&dq.front()<i-t) dq.pop_front();
		while (cur<=i-s)
		{
			while (!dq.empty()&&brd[dq.back()]>brd[cur]) dq.pop_back();
			dq.push_back(cur++);
		}
		if (!dq.empty()) brd[i]+=brd[dq.front()];
		else brd[i]=inf;
	}

    //跳出桥外,并寻找最优解
	int ans=inf;
	for (int i=l; i<l+t; i++)
	{
		while (!dq.empty()&&dq.front()<i-t) dq.pop_front();
		while (cur<l)
		{
			while (!dq.empty()&&brd[dq.back()]>brd[cur]) dq.pop_back();
			dq.push_back(cur++);
		}
		if (!dq.empty()) brd[i]+=brd[dq.front()];
		else brd[i]=inf;
		ans=min(ans, brd[i]);
	}


	//for (int i=0; i<l+t; i++) printf("%d ", brd[i]);
	//cout << endl;

   //输出
	printf("%d", ans);
	return 0;
	
} 


2023/9/30 23:38
加载中...