posts - 274,  comments - 1258,  trackbacks - 0

  Sicly今晚又有周赛了,兴致勃勃地找了一道题来做,却调了几个钟都找不到一个错误的数据,但总是返回Wrong Answer!只好贴到此处,请教各位大牛。

题目大意
给出平面上n(n<=105)个点的X、Y坐标(xi,yi)(0≤xi,yi≤109)及权值pi,求一条折线,满足:
1)折线只能向X正方向或Y正方向延伸;
2)折线的权值定义为折线上所有点的权值之和。
输出权值最大的折线的权值。

我的做法
先离散化,然后将n个点按第一顺序为X升序,第二顺序为Y升序来排序。
再建一棵线段树,每读一个项Pi =(xi, yi, pi);就在线段树里查询pi点的颜色C(yi),并加一条线段(yi,+∞),使得线段上每一点q的颜色C(qi)=max(C(yi)+pi,C(qi))。 最后输出C(+∞)即可。时间复杂度O(NlogN),空间复杂度O(N)。代码如下:

#include < cstdio >
#include
< cstring >
#include
< algorithm >
#include
< iostream >
using   namespace  std;
const   int  N = 100010 ; // 车站数
int  rx[N],ry[N],p[N],x[N],y[N],xp,yp;
struct  S { // 一个车站
   int  x,y,p;
  
bool   operator   < ( const  S &  o) const {
    
return  x == o.x ?  y < o.y : x < o.x;
  }

}
 t[N];

template
< int  N >
class  PntTree // 线段树的一种实现
     int  a[ 2 * N];
  
public :
    
/*  断言: i∈[0,N-1) (N-1用于表示+∞)  */
    
void  add( int  i, int  c) { // 添加点i
      c += C(i);
        
for (a[i += N] = c; i > 1 ; i /= 2 if ( ~ i & 1 if (c > a[i / 2 ]) a[i / 2 ] = c;  else   return ;
    }

    
int  C( int  i) { // 返回点i的颜色
         int  c = a[i + N];
        
for (i += N; i > 1 ; i /= 2 if (i & 1 ) c = max(c,a[i / 2 ]);
        
return  c;
    }

}
;
PntTree
< 131072 >  tr;
int  main() {
  
int  i,j,n,tx,ty;
  scanf(
" %d%d%d " , & tx, & ty, & n);
  
// 离散化
  xp = yp = 0 ;
  
for (i = 0 ; i < n;  ++ i) {
    scanf(
" %d%d%d " , & rx[i], & ry[i], & p[i]);
    x[xp
++ ] = rx[i];
    y[yp
++ ] = ry[i];
  }

  sort(x,x
+ xp);
  sort(y,y
+ yp);
  xp
= unique(x,x + xp) - x;
  yp
= unique(y,y + yp) - y;
  
for (i = 0 ; i < n;  ++ i) {
    t[i].x
= lower_bound(x,x + xp,rx[i]) - x;
    t[i].y
= lower_bound(y,y + yp,ry[i]) - y;
    t[i].p
= p[i];
  }

  
// 排序
  sort(t,t + n);
  
// 线段树操作
   for (i = 0 ; i < n;  ++ i) {
    
// cout<<t[i].x<<' '<<t[i].y<<' '<<t[i].p<<' '<<tr.C(t[i].y)<<"->";
    tr.add(t[i].y, t[i].p);
    
// cout<<tr.C(t[i].y)<<endl;
  }

  
// 输出无穷远处的颜色
  printf( " %d\n " ,tr.C(N - 1 ));
  
return   0 ;
}

附:题目全文

Task: The Bus


The streets of Byte City form a regular, chessboardlike network - they are either north-south or west-east directed. We shall call them NS- and WE-streets. Furthermore, each street crosses the whole city. Every NS-street intersects every WE- one and vice versa. The NS-streets are numbered from 1 to n, starting from the westernmost. The WE-streets are numbered from 1 to m, beginning with the southernmost. Each intersection of the i-th NS-street with the j-th WE-street is denoted by a pair of numbers (i, j) (for 1 <= i <= n, 1 <= j <= m).

There is a bus line in Byte City, with intersections serving as bus stops. The bus begins its itinerary by the (1, 1) intersection, and finishes by the (n, m) intersection. Moreover, the bus may only travel in the eastern and/or northern direction.

There are passengers awaiting the bus by some of the intersections. The bus driver wants to choose his route in a way that allows him to take as many of them as possible. (We shall make an assumption that the interior of the bus is spacious enough to take all of the awaiting passengers, regardless of the route chosen.)

Task

Write a programme which:

  • reads from the standard input a description of the road network and the number of passengers waiting at each intersection,
  • finds, how many passangers the bus can take at the most,
  • writes the outcome to the standard output.

Input

The first line of the standard input contains three positive integers n, m and k -- denoting the number of NS-streets, the number of WE-streets and the number of intersections by which the passengers await the bus, respectively. (1 <= n <= 109, 1 <= m <= 109, 1 <= k <= 105).

The following k lines describe the deployment of passengers awaiting the bus, a single line per intersection. In the i + 1st line there are three positive integers xi, yi and pi, separated by single spaces, 1 <= xi <= n, 1 <= yi <= m, 1 <= pi <= 106. A triplet of this form signifies that by the intersection (xi, yi)pi passengers await the bus. Each intersection is described in the input data once at the most. The total number of passengers waiting for the bus does not exceed 1 000 000 000.

Output

Your programme should write to the standard output one line containing a single integer - the greatest number of passengers the bus can take.

Example

For the input data:

8 7 11
4 3 4
6 2 4
2 3 2
5 6 1
2 5 2
1 5 5
2 1 1
3 1 1
7 7 1
7 4 2
8 6 2

the correct outcome is:

11


题目来源

posted on 2006-12-09 22:23 踏雪赤兔 阅读(710) 评论(3)  编辑 收藏 引用 所属分类: 玩转编程

FeedBack:
# re: 一道很郁闷的题
2006-12-10 01:04 | 踏雪赤兔
太可怕了,我连原题(POI)上面的数据都全过了~~怎么可能会WA?  回复  更多评论
  
# re: 一道很郁闷的题
2006-12-11 19:14 | 我的求职信
今天没白来,学到了  回复  更多评论
  
# re: 一道很郁闷的题
2006-12-12 02:10 | 踏雪赤兔
听起来很舒服,呵呵~  回复  更多评论
  
只有注册用户登录后才能发表评论。

百度空间| 见闻日记| 编程感悟
我的twitter


LOGO

自我介绍:百度厂基础平台车间的一名挨踢民工。擅长C++、算法、语言设计、分布式计算,也用过Java,Python, PHP,JS/AS等语言开发。请关注我的twitter (免翻墙版) 发QQ消息


添加到收藏夹 Locations of visitors to this page

常用链接

随笔分类(300)

随笔档案(274)

文章分类(38)

相册

收藏夹(54)

与博主互动

博客手拉手

搜索

  •  

积分与排名

  • 积分 - 392684
  • 排名 - 10

最新评论

阅读排行榜

评论排行榜