要改去世了啊啊啊
#include <iostream>
using namespace std;
struct Node { //AVL树结构体
int W;
int C;
int height;
struct Node* Right;
struct Node* Left;
};
typedef struct Node Flower;
typedef struct Node* Flowers; //方便书写,简洁化
static int Beauty, Price; //统计结果
int Max(int n, int m) { //max函数
if (n > m) {
return n;
}
else {
return m;
}
}
int High(Flowers T) { //获取节点高度
if (T == NULL) {
return -1;
}
else {
return T->height;
}
}
Flowers SingleRotateWithLeft(Flowers T) { //左单旋转
Flowers H;
H = T->Left;
T->Left = H->Right;
H->Right = T;
T->height = Max(High(T->Left), High(T->Right)) + 1;
H->height = Max(High(H->Left), High(H->Right)) + 1;
return H;
}
Flowers SingleRotateWithRight(Flowers T) { //右单旋转
Flowers H;
H = T->Right;
T->Right = H->Left;
H->Left = T;
T->height = Max(High(T->Left), High(T->Right)) + 1;
H->height = Max(High(H->Left), High(H->Right)) + 1;
return H;
}
Flowers DoubleRotateWithRight(Flowers T) { //右双旋转
T->Right = SingleRotateWithLeft(T->Right);
return SingleRotateWithRight(T);
}
Flowers DoubleRotateWithLeft(Flowers T) { //左双旋转
T->Left = SingleRotateWithRight(T->Left);
return SingleRotateWithLeft(T);
}
Flowers Insert(Flowers T, int w, int c) { //插入结点
if (T == NULL) { //递归终点
T = new Flower();
T->C = c;
T->W = w;
T->Right = T->Left = NULL;
}
else if (c < T->C) {
T->Left = Insert(T->Left, w, c); //左递归插入
if (High(T->Left) - High(T->Right) == 2) { //是否需要旋转调整
if (c < T->Left->C) {
T = SingleRotateWithLeft(T);
}
else {
T = DoubleRotateWithLeft(T);
}
}
}
else if (c > T->C) {
T->Right = Insert(T->Right, w, c); //右递归插入
if (High(T->Right) - High(T->Left) == 2) { //是否需要旋转调整
if (c > T->Right->C) {
T = SingleRotateWithRight(T);
}
else {
T = DoubleRotateWithRight(T);
}
}
}
T->height = Max(High(T->Left), High(T->Right)) + 1; //高度赋值
return T;
}
Flowers DeleteMax(Flowers T) { //递归删除树中C最大结点
if (T->Right == NULL) { //递归终点
Flowers H = T->Left;
delete T;
return H;
}
else {
T->Right = DeleteMax(T->Right);
T->height = Max(High(T->Left), High(T->Right)) + 1;
if (High(T->Left) - High(T->Right) == 2) { //判断删除后是否需要旋转
if (High(T->Left->Left) >= High(T->Left->Right)) { //单旋转
T = SingleRotateWithLeft(T);
}
else if (High(T->Left->Left) < High(T->Left->Right)) { //双旋转
T = DoubleRotateWithLeft(T);
}
}
T->height = Max(High(T->Left), High(T->Right)) + 1;
return T;
}
}
Flowers DeleteMin(Flowers T) { //递归删除树中C最小结点
if (T->Left == NULL) { //递归终点
Flowers H = T->Right;
delete T;
return H;
}
else {
T->Left = DeleteMax(T->Left);
if (High(T->Right) - High(T->Left) == 2) { //判断是否需要旋转
if (High(T->Right->Right) >= High(T->Right->Left)) { //单旋转
T = SingleRotateWithRight(T);
}
else if (High(T->Right->Right) < High(T->Right->Left)) { //双旋转
T = DoubleRotateWithRight(T);
}
}
T->height = Max(High(T->Left), High(T->Right)) + 1;
return T;
}
}
void Statistics(Flowers T) { //递归统计结果
if (T == NULL) { //递归终点
return;
}
else {
Beauty += T->W;
Price += T->C;
Statistics(T->Left);
Statistics(T->Right);
}
}
//void show(Flowers T) {
// if (T == NULL) {
// return;
// }
// cout << "W:" << T->W << " C:" << T->C << endl;
// show(T->Left);
// show(T->Right);
//}
int main() {
int operation, w, c;
Flowers T = NULL;
while (true) {
cin >> operation;
if (T == NULL && operation != 1) {
continue;
}
switch (operation) { //多路开关操作数
case 1: {
cin >> w >> c;
T = Insert(T, w, c);
break;
}case 3: {
T = DeleteMax(T);
break;
}case 2: {
T = DeleteMin(T);
break;
}case -1: {
Statistics(T);
//show(T);
cout << Beauty << " " << Price << endl;
return 0;
}
}
}
}