还有不要无意义讨论,从你我做起,谢谢
by AuKr @ 2020-04-06 11:41:55
@[AuKr](/user/317568) 不应该是根据T在当前x左右波动吗
by zsaskk @ 2020-04-06 11:54:11
[日报](https://www.luogu.com.cn/blog/m-sea/qian-tan-SA)
by zsaskk @ 2020-04-06 11:55:14
@[zsaskk](/user/134640)
是啊,可是我们每次将T乘delta,这样T就不一定是正整数了,那我们如何去保证x为正整数呢?
绝对值+取整???
by AuKr @ 2020-04-06 11:56:15
@[AuKr](/user/317568) 我刨一刨,我也好久没打了
by zsaskk @ 2020-04-06 11:57:23
@[AuKr](/user/317568)
```
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define int long long
#define chk_digit(c) (c>='0'&&c<='9')
#define eps 1e-14
#define changet 0.97
#define mymax(x,y) (x>=y?x:y)
#define mymin(x,y) (x>=y?y:x)
#define myabs(x) (x>=0?x:-x)
inline int read(){
reg int x=0,f=1;reg char c=getchar();
while(!chk_digit(c)) { if(c=='-') f=-1;c=getchar(); }
while(chk_digit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}
int n,m,ans,sum[1000001],now,av_pt,av_ans;
double stt;
struct node{
int val,height;
inline bool operator < (node tem) const{
return val<tem.val;
}
}a[1000001];
inline int RAND(int t) { return (t*(((rand()<<1)-RAND_MAX)%n)%n)%(n+1); }
priority_queue<node> q;
inline int get_ans(int x){
if(clock()-stt>=1890000) return 0;
int tmp=0,tm=m;
tmp+=sum[x];
while(q.size()) q.pop();
for(reg int i=1;i<=x;++i) if(a[i].height>1) q.push(a[i]);
tm-=x-1;
while(q.size()&&tm){
node x=q.top();q.pop();
int val=x.val,num=x.height-1;
if(tm>num) tmp+=num*val,tm-=num;
else tmp+=tm*val,tm=0;
}
return tmp;
}
inline void SA(){
for(reg double tem=8600;tem>eps;tem*=changet){
if(clock()-stt>=1890000) return;
int now1=now+(RAND(tem));
while(1) { if(now1>=1&&now1<=n) break;now1=now+(RAND(tem)); }
int tem_ans=get_ans(now1);
if(tem_ans>=ans) ans=tem_ans,now=now1;
else if(tem_ans>av_ans||exp(tem_ans-av_ans)/tem<rand()/RAND_MAX)
av_ans=tem_ans ,now=now1;
}
}
signed main(){
srand(time(0));
stt=clock();
n=read(),m=read();
for(reg int i=1;i<=n;++i) a[i].height=read(),a[i].val=read(),sum[i]=a[i].val;
for(reg int i=1;i<=n;++i) sum[i]+=sum[i-1];
av_pt=now=n+1>>1;av_ans=ans=get_ans(now);
for(;clock()-stt<=1000000;) SA();
printf("%lld\n",ans);
}
```
好久以前的代码,大约稳定70分左右,也没$AC$,你可以看一下。
可能写的不对。
by zsaskk @ 2020-04-06 12:01:32
@[zsaskk](/user/134640) 这是哪个题啊?
by AuKr @ 2020-04-06 12:02:10
@[AuKr](/user/317568) emm,[这题](http://ybt.ssoier.cn:8088/problem_show.php?pid=1673)~~正解不是模拟退火~~,可能和[钓鱼](https://www.luogu.com.cn/problem/P1717),类似,正解是贪心+优先队列,但我找不到我的$AC$代码了......
by zsaskk @ 2020-04-06 12:06:25
@[zsaskk](/user/134640) ok太感谢大佬了
by AuKr @ 2020-04-06 12:07:46
@[AuKr](/user/317568)
但其实我当时打那段代码时也好久没打了,其实挺怕误导你的。
~~说不定你可以把日报作者叫出来让他补一下~~
by zsaskk @ 2020-04-06 12:09:19