Source Code

Problem: 3277  User: yzhw 
Memory: 5020K  Time: 938MS 
Language: G++  Result: Accepted 

Source Code 
# include <iostream>
using namespace std;
# include <set>
# include <cstdio>
# include <cstdlib>
struct line
{
    int id;
    long long x;
    bool sta;
};
struct node
{
   long long p;
   int count;
};
class cmp1
{
public:
       bool operator()(node a,node b) const
       {
            return a.p>b.p;
       }
};
            
line data[100000];
long long h[100000];
int cmp(const void *a,const void *b)
{
    line *aa=(line *)a;
    line *bb=(line *)b;
    return aa->x-bb->x;
}
set<node,cmp1> res;
int main()
{
    int num;
    scanf("%d",&num);
    for(int i=1;i<=num;i++)
    {
       scanf("%lld %lld %lld",&data[2*i-1].x,&data[2*i].x,&h[i]);
       data[2*i-1].id=data[2*i].id=i;
       data[2*i-1].sta=1;
       data[2*i].sta=0;
    }
    qsort(data+1,2*num,sizeof(line),cmp); 
    long long total=0;
    for(int i=1;i<2*num;i++)
    {
       if(data[i].sta)
       {
         node temp;
         temp.count=1;
         temp.p=h[data[i].id];
         set<node,cmp1>::iterator it=res.find(temp);
         if(it==res.end())
            res.insert(temp);
         else
         {
             temp=*it;
             temp.count++;
             res.erase(temp);
             res.insert(temp);
         }
       }
       else
       {
         node temp;
         temp.count=1;
         temp.p=h[data[i].id];
         set<node,cmp1>::iterator it=res.find(temp);
         if(it->count==1)
           res.erase(temp);
         else
         {
            temp=*it;
            temp.count--;
            res.erase(temp);
            res.insert(temp);
         }
       }
	   if(data[i].x==data[i+1].x||res.empty()) continue;
       total+=(data[i+1].x-data[i].x)*(res.begin()->p);
    }
    printf("%lld\n",total);
    return 0;
} 

• 如果用薛矛大牛的术语说应该属于矩形切割。。。。 (2135) yzhw 2009-09-24 23:23:09