MnZn求助贪心
查看原帖
MnZn求助贪心
455490
Sharpsmile楼主2022/11/24 19:42

没有看出来哪里错了,样例全都是对的,查错了很久没有找到问题。

跪求各位大佬帮助。

QAQ

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <unordered_map>
#include <random>
#define int long long
#define double long double
#define p1(x) x.first
#define p2(x) x.second
#define i128 __int128_t
//#pragma GCC optimize(2)
#define w(x) w[x]
#define lz(x) lz[x]
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define pii pair<int,int>
using namespace std;
int n,m,k;
int s[100300];
int A,B,C,T;
int res;
int f[100300];
int nxt[100300];
signed main(){
	//freopen("/Users/liuyile/Downloads/problem_2396/sample2.in","r",stdin);
	//freopen("/Users/liuyile/Desktop/data.out","w",stdout);
	ios::sync_with_stdio(0);
	cin>>n>>m>>k;
	cin>>A>>B>>C;
	cin>>T;
	k-=m;
	for(int i=1;i<=m;i++)
		cin>>s[i],s[i]--;
	for(int i=1;i<m;i++)
		if(B*s[i]<=T)
		f[i]=min(s[i+1]-s[i]-1,(T-B*s[i])/A);
		else f[i]=-1;
	for(int j=1;j<=k;j++){
		int mx=-1,id=0;
		for(int i=1;i<m;i++)
		if(s[i]+f[i]!=s[i+1]-1){
			int t=T-s[i]*B-(f[i]+1)*C;
			if(t<0)continue;
			int loc=min(f[i]+1+t/A,s[i+1]-s[i]-1);
			if(loc-f[i]>mx)
				id=i,mx=loc-f[i];
			
		}
		if(id==0)break;
		f[id]+=mx;
	}
	int res=-1;
	for(int i=1;i<m;i++)
		res+=f[i]+1;
	if(s[m]*B<=T)
		res++;
	cout<<res;
	return 0;
}
2022/11/24 19:42
加载中...