#41484: 新思路,通用


seancai78@gmail.com (風月春秋)

學校 : 臺北市立成功高級中學
編號 : 176406
來源 : [140.113.124.212]
最後登入時間 :
2024-10-07 23:20:19
d555. 平面上的極大點 -- 名題精選百則 | From: [118.166.33.18] | 發表日期 : 2024-07-31 02:31

先建立兩個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

 
#41485: Re: 新思路,通用


seancai78@gmail.com (風月春秋)

學校 : 臺北市立成功高級中學
編號 : 176406
來源 : [140.113.124.212]
最後登入時間 :
2024-10-07 23:20:19
d555. 平面上的極大點 -- 名題精選百則 | From: [118.166.33.18] | 發表日期 : 2024-07-31 02:34

給一點閹割版的程式碼
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]];//直接跳,避免重複印出
        }
    }

 
ZeroJudge Forum