|
#2
寒风中的细雨2010-12-07 17:04
#include <iostream>
using namespace std; class Node { public: Node(int l=0, int r=0, int h=0, Node *p=NULL) { left = l; right = r; high = h; next = p; } //private: int left;// int right;// int high;// Node *next;//指向下个结点 }; class Wall { public: Wall() { area = 0;// head = new Node; } int Total();//计算面积 int Input(Node n);//处理新输入的结点 private: Node *head;//头结点 int area;//面积 }; int Wall::Total() { Node *temp = head->next; while(temp) { area += (temp->right - temp->left)*temp->high; temp = temp->next; } return area; } int Wall::Input(Node n) { Node *temp = head->next, *p = head; if( !temp ) {//直接插入在头结点后面 head->next = new Node(n.left, n.right, n.high, NULL); return 0; } int f_t = 0; while( n.left != n.right )//循环结束时候的条件 { if( temp->left > n.left ) { if( temp->left >= n.right ) { p->next = new Node(n.left, n.right, n.high, p->next ); n.left = n.right; p = p->next; } else if( temp->left < n.right && temp->right > n.right ) { p->next = new Node(n.left, temp->left, n.high, p->next ); n.left = temp->left; p = p->next; if( temp->high < n.high ) { p->next = new Node(n.left, n.right, n.high, p->next ); p = p->next; n.left = n.right; temp->left = n.right; } } else if( temp->right <= n.right ) { p->next = new Node(n.left, temp->left, n.high, p->next ); n.left = temp->left; p = p->next; if( temp->high < n.high ) { temp->high = n.high; } n.left = temp->right; if( !temp->next && n.left != n.right ) { temp->next = new Node(n.left, n.right, n.high, NULL); p = temp; temp = temp->next; n.left = n.right; } } } else if( temp->left == n.left ) { if( temp->right > n.right ) { if( temp->high < n.high ) { p->next = new Node(n.left, n.right, n.high, p->next ); p = p->next; temp->left = n.right; } n.left = n.right; } else if( temp->right <= n.right ) { if( temp->high < n.high ) { temp->high = n.high; } n.left = temp->right; if( !temp->next && n.left != n.right ) { temp->next = new Node(n.left, n.right, n.high, NULL); p = temp; temp = temp->next; n.left = n.right; } } } else if( temp->left < n.left && temp->right > n.left) { if( temp->right > n.right ) { if( temp->high < n.high ) { p->next = new Node( temp->left, n.left, temp->high, p->next ); p = p->next; p->next = new Node( n.left, n.right, n.high, p->next ); p = p->next; temp->left = n.right; } n.left = n.right; } else if( temp->right <= n.right ) { if( temp->high < n.high ) { p->next = new Node( temp->left, n.left, temp->high, p->next ); p = p->next; temp->left = n.left; temp->high = n.high; } n.left = temp->right; if( !temp->next && n.left != n.right ) { temp->next = new Node(n.left, n.right, n.high, NULL); p = temp; temp = temp->next; n.left = n.right; } } } else if( temp->right <= n.left ) { if( !temp->next ) { temp->next = new Node( n.left, n.right, n.high, NULL ); p = temp; temp = temp->next; n.left = n.right; } } p = p->next; temp = temp->next; } return 0; } int main() { Wall w; Node n; int i=0; cout << "输入断的个数: "; cin >> i; while( i-- ) { cin >> n.left >> n.right >> n.high; w.Input( n ); } cout << w.Total() << endl; return 0; } |
现在有一面墙,这面墙的高度并不是固定的。
区间 [l, r] 和这个区间的高度h。如果有重叠的部
分 ，取最高的高度。
★ 数据输入
输入 第一行有一个正整数 n(1<=n<=10000), 表示 n 个回复。
接下来 n 行，每行有三个数字 l r h ，表示区间 [l, r] 的高度为 h 。
计算过程中所有数据均在 int 范围之内。
★ 数据输出
输出墙的面积。
输入示例 输出示例
3
1 5 5
1 3 8
4 5 9
30
★ 样例说明
区间 [1, 5] 高度为 5 ， 区间 [1, 3] 高度为 8 ，区间 [4, 5] 高度为 9 。所以实际墙的高度应为
区间 [1, 3] 高度为 8 ，区间 [3, 4] 高度为 5 ，区间 [4, 5] 高度为 9 。总面积 S=8*(3-1)+5*(4-3)+9* (5-
4)=30 。
我自己想通过单向链表来实现。但不会处理区间面积交叉问题。
#include<iostream>
using namespace std;
class WALL
{
private:
public:
int left;
int right;
int height;
int area;
WALL *next;
WALL():left(0),right(0),height(0),next(0),area(0)
{
}
void get_data()
{
scanf("%d%d%d",&left,&right,&height);
area=(right-left)*height;
}
~WALL()
{}
};
int main()
{
int num;
int i=0;
WALL *head=NULL;
WALL *temp1,*temp2;
scanf("%d",&num);
while(i<num)//数据录入
{
temp1=(WALL *)malloc(sizeof(WALL));
if(head==NULL)
head=temp1;
else
temp2->next=temp1;
temp1->next=NULL;
temp1->get_data();
temp2=temp1;
++i;
}
return 0;
}
大家能帮忙想个函数来处理面积交叉的问题吗？