调整思想的运用
丢一道利用调整思想解的好题
#include <cstdio>#include <iostream>using namespace std;const int maxn = 100000 + 5;struct Heap { int data; };int n, X, Y, A, B, flood, Maxat;int c[maxn], cost;int tot;Heap heap[maxn];int Max(int a, int b) { return a > b ? a : b; }void Swap(Heap &x, Heap &y) { Heap t = x; x = y; y = t; }void Up(int p){ for (; (p >> 1) && heap[p >> 1].data < heap[p].data; Swap(heap[p >> 1], heap[p]), p >>= 1);}void Down(int p){ while (p << 1 <= tot) if (p << 1 < tot) { int q = heap[p << 1].data > heap[p << 1 | 1].data ? p << 1 : p << 1 | 1; if (heap[p].data < heap[q].data) Swap(heap[p], heap[q]), p = q; else break; } else if (p << 1 == tot) { if (heap[p << 1].data > heap[p].data) Swap(heap[p << 1], heap[p]); break; }}void Insert(int data){ heap[++tot].data = Max(Y, data); Up(tot);}void Getpop(){ int MAX = heap[1].data; heap[1] = heap[tot--]; Down(1); A += MAX; B += X;}void Win(int i){ cout << "Win" << endl << i << endl; exit(0);}void Lose(){ cout << "Lose" << endl << flood - Maxat << endl;}int main(){ freopen("fight.in", "r", stdin); freopen("fight.out", "w", stdout); cin >> n >> X >> Y >> A >> B; flood = Maxat = B; for (int i = 1; i <= n; ++i) scanf("%d", &c[i]); for (int i = 1; i <= n; ++i) { B -= X; Insert(c[i]); B < Maxat && (Maxat = B) <= 0 ? Win(i) : (void)0; for (A -= c[i]; A <= 0; Getpop()) if (!tot) return Lose (), 0; } Lose(); return 0;}