一种随机化思路
  • 板块P1833 樱花
  • 楼主lcezshiyuang
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/4/7 10:38
  • 上次更新2024/4/7 16:05:24
查看原帖
一种随机化思路
1253619
lcezshiyuang楼主2024/4/7 10:38

这个代码可以稳定AC但是还是想问问靠不靠谱,能不能推广

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t1hh,t2hh,t1mm,t2mm,n,tim;
char aa;
struct kq{
	int tie,bitf,num;
	double pjc;
};
vector<kq>a;
vector<kq>b;
void get_tim(){
int t1=t1hh*60+t1mm;
int t2=t2hh*60+t2mm;
 tim=t2-t1;	
}
bool cmp(kq aaa,kq ba){
	return aaa.pjc>ba.pjc;
}
signed main(){
	srand(time(0));
cin>>t1hh>>aa>>t1mm>>t2hh>>aa>>t2mm>>n;
get_tim();
for(int ii=1;ii<=n;ii++){
	kq i;
	cin>>i.tie>>i.bitf>>i.num;
	if(i.num==0) i.num=1e9;
	i.pjc=i.bitf*1.0/i.tie;
	a.push_back(i);
}
sort(a.begin(),a.end(),cmp);
int maxx=0;
int ti=tim;
for(auto v:a){
	b.push_back(v);
}
int yes=197;int yy=100000;
if(b.size()>1000) yy=10000;

for(int i=1;i<=yy;i++){
	a.clear();
	a.assign(b.begin(),b.end());
	int ans=0;
	tim=ti;
while(tim){
	while(rand()%yes==0&&a.size()>=2) swap(a[0],a[rand()%a.size()]);
	while((!a[0].num||tim<a[0].tie)&&!a.empty()) a.erase(a.begin());
	if(a.empty()) break;
	ans+=a[0].bitf;
	tim-=a[0].tie;
	a[0].num--;
}
//cout<<ans<<endl;
maxx=max(ans,maxx);
}

cout<<maxx;
	return 0;
}
2024/4/7 10:38
加载中...