先建立兩個int array
分別為max_x,max_y
max_x紀錄 在x = n時y的最大值,可以想成在x=n這條線最上面的點
max_y亦然
可以知道,當輸入(a,b)在(c,d)的右上方時
c < a且 b < d
那我們就可以用線的概念去確認這個店是否符合要求
實作方法就是:
(a,b)是唯一解
max_x[0~a] = b
max_y[0~b] = a
當輸入c d,會先尋找max[c] = b > d,不合
但有複數解的存在,因此在框選區域的時候要加一個max_x[i] = max(b, max_x[i]) (0<=i<=a)
max_y亦然,如此便可以框選出解的範圍
輸出答案
從i=0到i=100'001
if(max_x[i]!=-1)
輸出(max_y[max_x[i]],max_x[i])
用圖形的概念說:max_x是水平線段;max_y是鉛直線段,
選定一個x座標,找到max_x[x]的值(y座標),再去找y座標對應的鉛直線,那個點就是解
舉例:
0,8->one
1,10->two
3,4->three
one:max_x[0] = 8; max_y[0~8] = 0
two:max_x[0~1] = 10; max_y[0~10] = 1(這時候one已經不見了)
three:max_x[0~1] = 10, max_x[2~3] = 4; max_y[0~4] = 3, max_y[5~10] = 1
給一點閹割版的程式碼
int max_x[100'001],max_y[100'001];//同x/y座標時,最大的點
for (int i = 0; i < 100'001; i++)//初始化
{
max_x[i] = -1;
max_y[i] = -1;
}
int x,y;
for (int i = 0; i < count; i++)//輸入
{
scanf("%d %d",&x,&y);
if(max_x[x] < y && max_y[y] < x)//劃定
{
for (int j = 0; j <= x; j++)max_x[j] = max(max_x[j],y);
for (int j = 0; j <= y; j++)max_y[j] = max(max_y[j],x);
}
}
for (int i = 0; i < 100'001; i++)//輸出
{
if(max_x[i] != -1){
printf("%d %d\n",max_y[max_x[i]],max_x[i]);
i = max_y[max_x[i]];//直接跳,避免重複印出
}
}