首页 > ACM题库 > HDU-杭电 > HDU 3255-Farming-线段树-[解题报告]HOJ
2014
03-13

HDU 3255-Farming-线段树-[解题报告]HOJ

Farming

问题描述 :

You have a big farm, and you want to grow vegetables in it. You’re too lazy to seed the seeds yourself, so you’ve hired n people to do the job for you.
Each person works in a rectangular piece of land, seeding one seed in one unit square. The working areas of different people may overlap, so one unit square can be seeded several times. However, due to limited space, different seeds in one square fight each other — finally, the most powerful seed wins. If there are several "most powerful" seeds, one of them win (it does not matter which one wins).

There are m kinds of seeds. Different seeds grow up into different vegetables and sells for different prices.
As a rule, more powerful seeds always grow up into more expensive vegetables.
Your task is to calculate how much money will you get, by selling all the vegetables in the whole farm.

输入:

The first line contains a single integer T (T <= 10), the number of test cases.
Each case begins with two integers n, m (1 <= n <= 30000, 1 <= m <= 3).
The next line contains m distinct positive integers pi (1 <= pi <= 100), the prices of each kind of vegetable.
The vegetables (and their corresponding seeds) are numbered 1 to m in the order they appear in the input.
Each of the following n lines contains five integers x1, y1, x2, y2, s, indicating a working seeded a rectangular area with lower-left corner (x1,y1), upper-right corner (x2,y2), with the s-th kind of seed.
All of x1, y1, x2, y2 will be no larger than 106 in their absolute values.

输出:

The first line contains a single integer T (T <= 10), the number of test cases.
Each case begins with two integers n, m (1 <= n <= 30000, 1 <= m <= 3).
The next line contains m distinct positive integers pi (1 <= pi <= 100), the prices of each kind of vegetable.
The vegetables (and their corresponding seeds) are numbered 1 to m in the order they appear in the input.
Each of the following n lines contains five integers x1, y1, x2, y2, s, indicating a working seeded a rectangular area with lower-left corner (x1,y1), upper-right corner (x2,y2), with the s-th kind of seed.
All of x1, y1, x2, y2 will be no larger than 106 in their absolute values.

样例输入:

2
1 1
25
0 0 10 10 1
2 2
5 2
0 0 2 1 1
1 0 3 2 2

样例输出:

Case 1: 2500
Case 2: 16

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3255

 

题目大意:给你多块蔬菜地,蔬菜地有重叠部分,每部分种的蔬菜可能相同也可能不同,重叠部分种植蔬菜价值最贵的,最后让你求最大利润。

 

解题思路:

     这是我做的最坑爹的一题,几乎让我快哭了,Wrong answer了三十多次, 重拍了五六次代码。

     每块蔬菜地种植蔬菜收获的利润为 val=x*y*price。  面积乘以价格,题目的重点转换在于如何确定重叠区域怎么让它种植最贵的蔬菜。

     观察利润计算公式 :   x*y*price <==> x*y*h    可以转换为求体积并。

     说实话,这题一看真的很简单,一交就是一直错,代码每个部分都有调试N遍。 昨天一个就一直在调试,五个小时无果。和别人一对照,思路一点都没错,今天下午再重拍了一遍代码,又开始了Wrong answer之路,然后带着那颗受伤的心去改数组范围。点最大3W, 我线段树开12W多,存X的点开6W多。 点开4W错, 6WTLE, 索性所有数组范围开150005,错。 150101 AC。 我想哭了…..

 

FarmingView Code

#include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <algorithm>
 using namespace std;
 
 #define lson l,mid,ID<<1
 #define rson mid+1,r,ID<<1|1
 const int maxn=150101;
 typedef long long lld;
 int flag[maxn];
 lld sum[maxn];
 int X[maxn], Z[maxn];
 
 struct Node   ///这题快把我整哭了
 {
     int lx, rx, y, z, s;
     Node(){}
     Node(int lx_, int rx_ , int y_, int z_, int s_)
     {
         lx=lx_, rx=rx_, y=y_, z=z_, s=s_;
     }
     bool operator<(const Node &S) const
     {
         if(y==S.y) return s>S.s;
         else return y<S.y;
     }
 }line[maxn], tmp[maxn];
 
 
 int find(int x, int M)
 {
     int l,r,m;
     l=1;
     r=M;
     while(l<=r)
     {
         m=(l+r)>>1;
         if(X[m]==x)
             return m;
         if(X[m]<x)
             l=m+1;
         else
             r=m-1;
     }
 }
 void Push_up(int ID,int l,int r)
 {
     if(flag[ID])sum[ID]=X[r+1]-X[l];
     else if(l==r)sum[ID]=0;
     else sum[ID]=sum[ID<<1]+sum[ID<<1|1];
 }
 void Update(int x,int y,int z,int l,int r,int ID)
 {
     int mid;
     if(x<=l&&r<=y)
     {
         flag[ID]+=z;
         Push_up(ID,l,r);
         return ;
     }
     mid=(l+r)>>1;
     if(x<=mid)
         Update(x,y,z,lson);
     if(y>mid)
         Update(x,y,z,rson);
     Push_up(ID,l,r);
 }
 
 int main()
 {
     int n, m, T, tcase=0;
     cin >> T;
     while(T--)
     {
         cin >> n >> m;
         Z[0]=0;
         for(int i=1; i<=m; i++)
             cin >> Z[i];
         int num=0;
         for(int i=0; i<n; i++)
         {
             int x1, x2, y1, y2, id;
             scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&id);
             line[++num]=Node(x1,x2,y1,Z[id],1);
             X[num]=x1;
             line[++num]=Node(x1,x2,y2,Z[id],-1);
             X[num]=x2;
         }
         sort(Z,Z+m+1);
         sort(X+1,X+num+1);
         sort(line+1,line+num+1);
         int ep=1;
         for(int i=2; i<=num; i++)
             if(X[i]!=X[ep]) X[++ep]=X[i];
         lld ans=0;
         for(int i=0; i<m; i++)
         {
             memset(sum,0,sizeof(sum));
             memset(flag,0,sizeof(flag));
             lld tp=0, cnt=0;
             for(int j=1; j<=num; j++)
                if(line[j].z>Z[i]) tmp[++cnt]=line[j];
             for(int j=1; j<cnt; j++)
             {
                 int l=find(tmp[j].lx,ep);
                 int r=find(tmp[j].rx,ep)-1;
                 Update(l,r,tmp[j].s,1,ep-1,1);
                 tp+=sum[1]*(lld)(tmp[j+1].y-tmp[j].y);
             }
             ans+=tp*(lld)(Z[i+1]-Z[i]);
         }
         printf("Case %d: %I64d\n",++tcase,ans);
     }
     return 0;
 }

 

参考:http://www.cnblogs.com/kane0526/archive/2013/03/07/2948446.html