首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

整合思想的运用

2012-10-17 
调整思想的运用丢一道利用调整思想解的好题#include cstdio#include iostreamusing namespace stdcon

调整思想的运用

丢一道利用调整思想解的好题

#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;}

还要感谢DRJ,与SYJ的堆代码,终于把以前的大常数maintain堆改了



1楼a2520123前天 21:34
这种堆都写得这么丑= =
Re: z635457712a前天 21:36
回复a2520123n= =你说的丑是平时drj说的丑还是效率嗍?
Re: a2520123前天 21:56
回复z635457712an看着丑
Re: z635457712a前天 22:08
回复a2520123nC++的缩行你永远不懂= =

热点排行