24h購物| | PChome| 登入
2011-10-16 09:32:40| 人氣502| 回應0 | 上一篇 | 下一篇

a245. 王老師愛兩條線

推薦 0 收藏 0 轉貼0 訂閱站台

a245. 王老師愛兩條線

內容 ：

最近，柏油高中的數學老師們忽然愛上了兩條線，於是柏油高中的學生們就倒楣了......他們的作業全部都是滿滿的兩條線，不管是題目還是答案，就連廁所每個磁磚的兩側，每個學生的頭上，都是滿滿的兩條線。

  這真的是太愚蠢了......。

於是在虹原大學上課的你，你的筆電「嘟」的一聲，學弟傳訊息過來了：

「學長救命呀！」

「什麼狗啊......」你不知不覺說了這句，就把筆電闔上。 

就在下一秒，你的手機響了，被全班盯著看。

「呃......」你嬌羞地淚奔出教室接電話。

「你ㄎㄧ笑了嗎= =，居然在上課時間打電話給我！」接起手機，你馬上開始大吼。

「對不起麻學長......快點救救我，我們學校裡面某個王老師才真的ㄎㄧ笑，自從你離開這座學校之後，他看到了神作三條線，他就忽然發瘋，在學校傳教兩條線的好處，現在整個學校都在『兩條線收束協會』的統治之下，......」學弟的故事還沒說完，你已經露出不耐煩的神色，打斷學弟的發言。

「講重點好嗎？！我剛剛衝出來接電話的事情已經被教授知道了，要是講太久的話又會被那位男教授約出去喝咖啡的啦。」

「唉呦不要這樣麻，我知道學長人正，心地又好，一定會幫我的說。那我繼續講下去：因為在『兩條線收束協會』的影響之下，我們期中考的題目全部都變成了兩條線......」

「那還不簡單，直接把負號去掉就好了呀。」再次打斷學弟發言。

「NOOOOOOO不對呀！！事情不是憨人所想的那麼簡單，因為題目都變成了兩條線，使得這座學校的學生思想退化回18世紀，而我和其他幾個人是少數和『協會』抗爭的人，因此才沒有被洗腦，但是要改變『協會』統治的現實，我們必須要找回消失的第三條線......」

「喔？是嗎？那你就去其他地方找呀。」你交談的同時，隨手將自己另外一支手機拿出來，順手按了三個數字。

  「不，我已經找到了......那就是......」當然，正常人能聽到這裡就已經很厲害了，你早就很想掛掉了。

正當轉身回去上課時，你的視線變得模糊，整個空間開始在旋轉。你四肢開始扭曲，身體往一邊傾倒，最後做倒在地面上，表情顯露出極大的不舒服。

一段時間後，周圍的視線開始漸漸清晰，空間也漸漸正常，此時你發現自己倒在柏油高中的大馬路上，穿著以前的制服。

「這是什麼狗呀......」你咕噥了一聲，看起來一副在九彎十八拐走九遍的模樣，身體平衡還無法恢復正常。

此時，剛剛學弟打電話過來的手機響了，是簡訊。

發信人：F8

簡訊內容如下：

『 

嘿嘿嘿......你已經被『協會』給盯上了，

如果你沒有回答出接下來的問題，那麼...

...嘿嘿嘿......

』 

「這又是啥狗......」怪了，今天奇怪的事實在太多了。這時又傳來另外一封簡訊，發信者依然是F8。

『

給你三個點(0, 0), (1, 1), (2, 2)，請找出某

點P，使得點P跟其他三個點的距離和為最

小。若有答案請回覆。 

』 

「啥狗......」你已經說了四遍，很順手地就把 2 * sqrt(2) 傳了過去。

此時，強風把你的鞋帶吹掉了，正當你低頭綁鞋帶時，說時遲那時快，「啪」的一聲，你看見自己面前不遠處有一道彈痕，從燒焦的痕跡以及冒煙狀況來看，是剛剛形成的。

是剛剛形成的。

是剛剛形成的。

是剛剛形成的！

「什麼鬼呀......」你終於換了另外一句台詞，這時又來了另外一封簡訊：

『

You!!!
Can not PASS!!!!!!! 

同學，乖乖繼續念你的高五吧=ˇ=

愛你的王老師 

』

「什麼！！！NOOOOOOOOOOOOOOOOOOOOOOO~~~~~~老師不要當我呀！！！！」上大學之後，你對於「Pass」這個字眼變得非常敏感，所以崩潰了。

  其他人幫他看看，到底是為什麼算錯了呢？ 

輸入說明 ：

輸入有多筆測資，一開始會有單獨一行的數 T <= 10000，代表測試組數。

接著每筆測試資料中，第一行僅有一整數 N <= 1000，代表輸入點數。接著 N 行，每行有兩個整數 -10000 <= X, Y <= 10000，代表點的座標。

輸出說明 ：

對於每組測資，請輸出包含兩個整數的一行。前面的整數代表產生最小的距離和，後面的整數代表有幾種可能的整數解可以產生最小答案。

範例輸入 ： 

1
3
0 0
1 1
2 2

範例輸出 ：

4 1

提示 ：

測資顯示最小的距離是在 (1, 1) 這個位置。距離和為 |2-1| + |2-1| + |0-1| + |0-1| = 4。

出處 ：

板橋高中練習題 (管理：m80126colin)


找整數座標到所有點的曼哈頓距離和最小，順便求出有多少個這種點
作法 : DP
這題不一定要 DP，用中位數也可以寫
因為 X 跟 Y 軸無關，因此分開做，找到一個 X 座標到所有點的 X 座標和最小，
把兩次算的個數加總跟相乘就是答案了。
/**********************************************************************************/
/*  Problem: a245 "王老師愛兩條線" from 板橋高中練習題              */
/*  Language: C (1528 Bytes)                                                      */
/*  Result: AC(2.2s, 412KB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2011-10-15 23:32:40                                     */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 2147483647
int cmp(const void *i, const void *j) {
    return *(int *)i - *(int *)j;
}
int main() {
    int t, n, X[1001], Y[1001], i;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        int sumx = 0, sumy = 0;
        for(i = 0; i < n; i++) {
            scanf("%d %d", &X[i], &Y[i]);
            sumx += X[i];
            sumy += Y[i];
        }
        qsort(X, n, sizeof(int), cmp);
        qsort(Y, n, sizeof(int), cmp);
        sumx -= X[0]*n, sumy -= Y[0]*n;
        int Ans1 = 1, Ans2 = 1, minx = sumx, miny = sumy;
        for(i = 1; i < n; i++) {
            sumx = sumx + (X[i] - X[i-1])*i - (X[i] - X[i-1])*(n-i);
            if(sumx == minx)
                Ans1 += X[i] - X[i-1];
            else if(sumx < minx)
                minx = sumx, Ans1 = 1;
        }
        for(i = 1; i < n; i++) {
            sumy = sumy + (Y[i] - Y[i-1])*i - (Y[i] - Y[i-1])*(n-i);
            if(sumy == miny)
                Ans2 += Y[i] - Y[i-1];
            else if(sumy < miny)
                miny = sumy, Ans2 = 1;
        }
        printf("%d %d\n", minx + miny, Ans1*Ans2);
    }
    return 0;
}/*
2
3
0 0
1 1
2 2
*/
/**********************************************************************************/
/*  Problem: a245 "王老師愛兩條線" from 板橋高中練習題              */
/*  Language: CPP (1493 Bytes)                                                    */
/*  Result: AC(1.2s, 1.4MB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2011-10-15 23:41:02                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
#define oo 2147483647
int cmp(const void *i, const void *j) {
    return *(int *)i - *(int *)j;
}
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int t, n, X[1001], Y[1001], i;
    ReadInt(&t);
    while(t--) {
        ReadInt(&n);
        int sumx = 0, sumy = 0;
        for(i = 0; i < n; i++) {
            ReadInt(&X[i]), ReadInt(&Y[i]);
            sumx += X[i];
            sumy += Y[i];
        }
        qsort(X, n, sizeof(int), cmp);
        qsort(Y, n, sizeof(int), cmp);
        sumx -= X[0]*n, sumy -= Y[0]*n;
        int Ans1 = 1, Ans2 = 1, minx = sumx, miny = sumy;
        for(i = 1; i < n; i++) {
            sumx = sumx + (X[i] - X[i-1])*(2*i-n);
            if(sumx == minx)
                Ans1 += X[i] - X[i-1];
            else if(sumx < minx)
                minx = sumx, Ans1 = 1;
        }
        for(i = 1; i < n; i++) {
            sumy = sumy + (Y[i] - Y[i-1])*(2*i-n);
            if(sumy == miny)
                Ans2 += Y[i] - Y[i-1];
            else if(sumy < miny)
                miny = sumy, Ans2 = 1;
        }
        printf("%d %d\n", minx + miny, Ans1*Ans2);
    }
    return 0;
}


我要檢舉
#a245#王老師愛兩條線
台長： Morris

您可能對以下文章有興趣

人氣(502) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:a277. 高手寂寞
此分類上一篇:a254. 畢氏‧三角‧製造

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文