样例没过,提交后满分,样例hack我算法?
查看原帖
样例没过,提交后满分,样例hack我算法?
1220105
20230332fuben楼主2024/1/9 09:17

我介绍一下我的算法,很明显我们打一个差分数组dif,然后按顺序就算差分数组dif前缀和,即为总共借出去的教室,当算到某一个借出去的教室数量大于那天的教室数量,输出-1并且停止计算,我们就知道在这一天,不符合情况,那么我们从头遍历订单,如果订单中借教室的天数包含该天,我们就减去借出去的教室,当减到小于0时,停止运算,该订单就是第一个不满足的订单号, 提交满分,样例 4 3 2 5 4 3 2 1 3 3 2 4 4 2 4 输出-1 3??? 大佬们怎么回事

#include<iostream>
using namespace std;
const int nnu=1000000+9;
int n,m,d[nnu],l[nnu],r[nnu],ju=0;
int dif[nnu]={0},sumdif[nnu]={0},room[nnu],froom[nnu];

int main(void)
{
	cin>>n>>m;
	for(int a=1;a<=n;a++)cin>>room[a],froom[a]=room[a];
	for(int a=1;a<=m;a++)
		cin>>d[a]>>l[a]>>r[a],dif[l[a]]-=d[a],dif[r[a]+1]+=d[a];
	for(int a=1;a<=n;a++)
	{
		sumdif[a]=dif[a]+sumdif[a-1];
		room[a]+=sumdif[a];
		if(room[a]<0)
		{
			cout<<-1<<endl;
			int tem=froom[a];
			for(int i=1;i<=m;i++)
			{
				if(a>=l[i]&&a<=r[i])tem-=d[i];
				if(tem<0)
				{
					cout<<i;
					return 0;
				}
			}
		} 
	}
	cout<<0;
	return 0;
} 
2024/1/9 09:17
加载中...