欧洲退火!

没错你没有看错这么一道Heap的题我拿出了退火来做!

那么模拟退火的基本思路这里不讲了如果要看右转P1337去看。

废话不多说,上思路

这个思路有些类似P2503的思路,基本的操作就是_“交换”_,在这道题里就是把一个在以前的最优解中,把一个用了优惠券的牛的优惠券转而用到另一只没有用优惠券的牛身上。

而至于估价的话我们就采用贪心,直接取最便宜的几头牛就是了。

但是你会惊奇的发现如果这样你会死活调不出来,在WA与TLE之间挣扎,只有62分。

而且SA的过程中已经没有什么可以优化了,于是我们只能考虑在SA的过程外优化

自然而然联想到可以用一个错的离谱的贪心来选择初始状态

在这里我选用的是以$p_i + c_i$为关键字进行升序排序,于是就A了

AC记录

接下来上代码吧2333

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>

using namespace std;

struct Node{
int p;
int c;
}s[60000];

bool cmp(Node a, Node b){ // 错误贪心排序
return (a.p + a.c) < (b.p + b.c);
}

bool Cpn[60000]; // 维护当前每头牛有没有用优惠券
int Usc[60000]; // 用了优惠券的牛
int Duc[60000]; // 没有用优惠券的牛
int n, k;
long long m;

int Ans;

int Calc(){ // 为当前状态估价
int Num[60000];
for(int i = 1; i <= n; i++)
Num[i] = Cpn[i] ? s[i].c : s[i].p;
sort(Num+1, Num+n+1);
int Ans = 0;
long long Res = 0;
for(int i = 1; Res <= m && i <= n; i++){
Res += (long long)Num[i];
Ans++;
}
if(Res <= m) return Ans;
return Ans - 1;
}

void SA(){
for(double Temp = 2000; Temp >= 1; Temp *= 0.9){ // 退火
int x = rand() % k + 1; // 在用了优惠券的牛里面选一头
int y = rand() % (n - k) + 1; // 在没用……
swap(Usc[x], Duc[y]);
Cpn[Usc[x]] = true;
Cpn[Duc[y]] = false;
int Nxt = Calc();
int Del = Nxt - Ans;
if(Del > 0)
Ans = Nxt;
else if(exp(-(double)Del / Temp) * RAND_MAX * 2 < rand()){ // 有概率接受一个更差解
swap(Usc[x], Duc[y]);
Cpn[Usc[x]] = true;
Cpn[Duc[y]] = false;
}
}
}

int main(){
srand(20050426 + 20031119); // LJC00118 + Saofish的生日
scanf("%d %d %lld", &n, &k, &m);
for(int i = 1; i <= n; i++)
scanf("%d %d", &s[i].p, &s[i].c);
sort(s+1, s+n+1, cmp); // 玄学排序
for(int i = 1; i <= k; i++){ // 默认将前k个设为用了优惠券的
Usc[i] = i;
Cpn[i] = true;
}
for(int i = k+1; i <= n; i++){ // 其余的不用
Duc[i - k] = i;
Cpn[i] = false;
}
Ans = Calc(); // 为初始状态估价
SA(); // 退火
printf("%d", Ans);
}

 评论