轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年12月10日 星期三

TIOJ::1062 . 用餐地點(Lunch)

http://tioj.ck.tp.edu.tw/problems/1062

這題超水的....。



本來,想了一堆解法,甚麼N^4的都出來了,結果根本就是除了輸入N^2之外O(N)就做完的水題阿....。

這題最難的就是題目,真的看不懂他再寫甚麼。
題目應該是說,有一群人要吃午餐,我們要找一個點設置午餐,而人們移動到相鄰的格子要花費一單位時間,求一個點讓大家花的時間最少,注意是大家花的時間,所以就是所有人的時間加起來。
基本上就是每個格子到午餐的曼哈頓距離乘上該格的人數。不過有個很基本的性質,首先是XY軸可以分開看,不影響。再來就是,只要中位數在的那格,一定是最佳解(把總人數加起來,找出中位數,讓一半的人再前面,一半再後面)。
所以我們先把每一行加起來,找出中位數再哪一格,再把每一列加起來,一樣找出中位數,就可以知道X Y座標了。

然後這題是1base。

進階版。

#include <cstdio>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
int X[100],Y[100],a,b,m,n,tmp,sum;
main(){
    scanf("%d%d",&n,&m);
    F(n)Fi(j,m)scanf("%d",&a),X[i]+=a,Y[j]+=a,sum+=a;
    sum=(sum+1)>>1;
    F(n){
        if(tmp+X[i]<sum)tmp+=X[i];
        else{
            printf("%d ",i+1);
            break;
        }
    }
    tmp=0;
    F(m){
        if(tmp+Y[i]<sum)tmp+=Y[i];
        else{
            printf("%d\n",i+1);
            break;
        }
    }
    scanf("%*d");
}

沒有留言:

張貼留言