NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組決賽
 NPSC 2008 高中組 決賽 E.不景氣的年代

作者 主題: NPSC 2008 高中組 決賽 E.不景氣的年代  (閱讀 9689 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
NPSC 2008 高中組 決賽 E.不景氣的年代
« 於: 十一月 30, 2009, 01:47:56 pm »

NPSC 2008 高中組 決賽 E.不景氣的年代

說明:給你很多組的正整數 a、b、c,且 a+b+c <= 10000,請你找出一組 Pa、Pb、Pc , Pa>=a、Pb>=b、Pc>=c 且 Pa+Pb+Pc<=10000,問你這組數字最多可以滿足幾組數字。

解法:將所有資料依 a 的值由大到小排序,再將 a 的值固定,去尋找最大可以滿足多少組 b、c 的值即可。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2008 高中組決賽
// 題目 E - 不景氣的年代
// By sagit at TCGS
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX=5001, MONEY=10000;
struct ABC { int a, b, c; } P[MAX];     // 記錄每個人的需求
bool Comp1(ABC x, ABC y) { return x.a>y.a; } // 排序用 for P
struct BC { int b, c; } P2[MAX];        // 記錄部分人 b、c 的值
bool Comp2(BC x, BC y) { return x.b<y.b; } // 排序用 for P2
int Pn, Pn2;                            // Pn 記錄總人數, Pn2 記錄 P2 人數
int C[MAX], Cn;                         // 記錄已排序的 c 值

int main()
{
    freopen("pe.in", "rt", stdin);
    freopen("pe.out", "w+t", stdout);
    ios_base::sync_with_stdio(false);
    int k, i, j, x, y, c, mid, Ans, Max;
    cin >> k;
    while (k--)
    {
        cin >> Pn;
        for (i=0; i<Pn; i++)            // 輸入每位國民的需求
            cin >> P[i].a >> P[i].b >> P[i].c;
        sort(P, P+Pn, Comp1);           // 依 a 的值由大到小排序
        for (i=0, Max=0; i<Pn && Pn-i>Max; i++) // 將 a 固定來找答案
        {
            for (j=i, Pn2=0; j<Pn; j++) // 將 b、c 的值複製到 P2
            {
                if (P[i].a+P[j].b+P[j].c>MONEY) continue;
                P2[Pn2].b=P[j].b;
                P2[Pn2].c=P[j].c;
                Pn2++;
            }
            sort(P2, P2+Pn2, Comp2);    // 依 b 的值由小到大排序
            for (j=0, Cn=0, Ans=0; j<Pn2; j++)
            {
                for (x=Cn-1; x>=0; x--) // 將 c 的值插入已排序的 C 陣列
                {
                    if (C[x]<=P2[j].c) break;
                    C[x+1]=C[x];
                }
                Cn++;
                C[x+1]=P2[j].c;
                c=MONEY-P[i].a-P2[j].b+1; // 計算剩下可用的 c 還有多少
                y=Cn-1;
                while (x<=y)    // Binary Search - 尋找不大於 c 的有多少人
                {
                    mid=(x+y)/2;
                    if (C[mid]<c) x=mid+1;
                    else if (C[mid]>c) y=mid-1;
                    else break;
                }
                while (C[mid]<=c&&mid<Cn) mid++; // 略過小於等於 c 的人
                if (mid>Ans) Ans=mid;
            }
            if (Ans>Max) Max=Ans;
        }
        cout << Max << endl;
    }
//    system("PAUSE");
    return 0;
}
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 E.不景氣的年代
« 回覆 #1 於: 十一月 30, 2009, 01:49:03 pm »

這一題在我自己的電腦上執行,
約 12 秒左右,
但是在 ZeroJudge 上只有 7 秒,
故在比較快的電腦上執行是可以 AC 的....

本解法的時間複雜度上限為 O(N^3),
故排序及搜尋的部分儘量改用 O(nlogn) 及 O(logn) 演算法,
以加快處理....

如果各位網友有更快的解法,
也歡迎分享....
記錄

electron

  • 新手
  • *
  • 文章數: 5
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 E.不景氣的年代
« 回覆 #2 於: 十二月 20, 2009, 12:50:19 am »

不知道是否有存在 O(NlogN) 方法,看解題上面有人 8ms 就過掉  :-\
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 E.不景氣的年代
« 回覆 #3 於: 十二月 20, 2009, 03:09:14 pm »

看了一下他們程式碼的長度,
都只有200Bytes左右,
應該是直接用官方的測資輸出的吧....
記錄

b821213

  • 初級會員
  • **
  • 文章數: 21
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 E.不景氣的年代
« 回覆 #4 於: 九月 30, 2010, 07:01:56 pm »

不好意思 想問一下

// 將 c 的值插入已排序的 C 陣列

這句本身以及之後的程序不是很了解意思
能夠幫忙說明一下嗎?

記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 E.不景氣的年代
« 回覆 #5 於: 十月 01, 2010, 01:46:48 pm »

裁判的說法是, 把一個值固定,
另外兩個值去暴搜,
我之前寫的版本是用兩層的for迴圈去跑B、C兩個值,
不過會有一點點超時,
所以後來把它改良一下,
上面的寫法是, 將A固定之後,
小於等於該A值的抽出來再依B值從小到大排序,
一方面慢慢擴大B值大小,
另一方面把到目前為止出現過C值丟進另一個已排序的陣列,
因為A、B的值已經固定, 所以我們可以算出C值最大是多少,
又因為這個陣列已經排序好了, 所以只要 LgN 就可以出符合的數量,
整個程式的時間複雜度為 N^2*LgN ....

當然你可以再去想有沒有比較快的方法,
基本上就是暴搜和一些優化的處理吧.....
記錄

b821213

  • 初級會員
  • **
  • 文章數: 21
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 E.不景氣的年代
« 回覆 #6 於: 十月 01, 2010, 09:15:20 pm »

那最壞狀況下這樣子是不是反而會更糟糕呢?
我的意思是 如果每次新加入的c值都剛好是新的最小值的話
就變成說每次都要花n的時間插入 跟直接搜尋反而一樣了
還是我的理解有錯誤?
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 E.不景氣的年代
« 回覆 #7 於: 十月 02, 2010, 12:54:38 am »

我覺得這一題和2009年決賽的「大風吹」是類似的,
都是在考一個有優化(或Cut)的暴搜,
當然如果事先知道對方是用什麼方式優化,
就可以找出讓他暴掉的測資,
但是相反的如果事先知道測資是長什麼樣子,
也可以很容易針對它做出優化....

我是覺得, 只要考慮一般的情況就好了,
當然我的解法只能算是"可行解", 而不是"最佳解",
你看看ZeroJudge上該題很多人的程式都跑得比我快就知道了....

話說回來, 你說的是有可能的,
也許有人可以設計某種資料結構,
可以在 lgN 的時間插入元素,
也可以在 lgN 的時間找出符合條件的個數,
或者有更好的解法也不一定,
就靠各位提供了....
« 上次編輯: 十月 02, 2010, 12:56:17 am 由 sagit »
記錄

b821213

  • 初級會員
  • **
  • 文章數: 21
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 E.不景氣的年代
« 回覆 #8 於: 十月 02, 2010, 05:39:26 pm »

恩恩 謝謝sagit大的講解 :)

說到優化的暴搜 老實說我覺得嚴格說起來這也算是很難的一個部分
怎麼說呢 因為它沒有一定的法則 也無法看書學會(當然經驗是有差別的)
有些cut甚至還要看個人的創意
就像acm的一題木棍原長的問題 dfs以外還要加一大堆剪枝才過得了
這類的問題如果限制嚴格一點 也許競賽期間要解出來反而會比困難的算法還要難
記錄

yuscvscv

  • 初級會員
  • **
  • 文章數: 30
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 E.不景氣的年代
« 回覆 #9 於: 十月 16, 2010, 06:14:52 pm »

話說回來, 你說的是有可能的,
也許有人可以設計某種資料結構,
可以在 lgN 的時間插入元素,
也可以在 lgN 的時間找出符合條件的個數,
或者有更好的解法也不一定,
就靠各位提供了....

使用線段樹或樹狀數組即可XD

插入 lgM,詢問 lgM ,(M <= 10000)
記錄

b821213

  • 初級會員
  • **
  • 文章數: 21
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 E.不景氣的年代
« 回覆 #10 於: 十月 19, 2010, 07:42:12 am »

感謝yuscvscv大的指導 這題用了類似線段數的作法後真的快了很多(雖然還是不知道ZJ上面1.X秒的是怎麼回事...好像直接輸出解答不會這麼慢XDD)

以下是程式碼
代碼: [選擇]
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

struct line{
  int s,t;
};

struct data{
  int a,b,c;
};

int sum[50000];
line t[50000];
data sa[10000];
data sb[10000];

int getn(void){
  int temp=0;
  char in;
  while(1){
    scanf("%c",&in);
    if(in==10||in==32) return temp;
    temp=temp*10+in-'0';
  }       
}

void build_t(int s,int f,int no){  //先把每個子葉上的範圍定好
 
  t[no].s=s;
  t[no].t=f;
  if(s==f-1) return;
  build_t(s,(s+f)/2,no*2);
  build_t((s+f)/2,f,no*2+1);       

}

void t_push(int s,int f,int no){   //插入數值 途中經過的所有葉子都要+1
 
  ++sum[no];   
  if(t[no].s==s && t[no].t==f) return;
  int mid=(t[no].s+t[no].t)/2;
  if(s>=mid) t_push(s,f,no*2+1);
  else t_push(s,f,no*2);

}

int t_find(int s,int f,int no){   //二分搜尋合法的c值
 
  if(s==t[no].s && f==t[no].t) return sum[no];
  int mid=(t[no].s+t[no].t)/2;
  if(s>=mid) return t_find(s,f,no*2+1);
  else if(f<=mid) return t_find(s,f,no*2);
  else return t_find(s,mid,no*2)+t_find(mid,f,no*2+1);

}

bool cmpa(data t1,data t2){return t1.a > t2.a;}
bool cmpb(data t1,data t2){return t1.b < t2.b;}
     
int main(){
 
  build_t(0,10001,1); 
 
  int n;
  n=getn();
  while(n--){   
    memset(sum,0,sizeof(sum));
    int k;
    int ans=0;
    k=getn(); 
    for(int i=0;i<k;++i)
      sa[i].a=getn(),sa[i].b=getn(),sa[i].c=getn();
   
    memcpy(sb,sa,sizeof(sa));
    sort(sa,sa+k,cmpa);
    sort(sb,sb+k,cmpb);
 
    int bk[10000];
    int bn=0;
    for(int i=0;i<k;++i)   //把要考慮的b值存起來 因為會調用很多次所以另外開陣列
      if(bn==0 || sb[i].b != bk[bn-1]) bk[bn++]=sb[i].b;
   
    for(int i=0;i<k;++i){
      if(i&&sa[i].a==sa[i-1].a) continue;
      int a=sa[i].a;
      int bp=0;  //以b值作排序的陣列指針 記錄現在已經到哪個位置 下次就從這裡開始繼續插入c值
      memset(sum,0,sizeof(sum));       
      for(int j=0; j<bn && a+bk[j]<=10000;++j){
         int b=bk[j];
         for(;bp<k && sb[bp].b<=b;++bp)
           if(sb[bp].a <= a) t_push(sb[bp].c,sb[bp].c+1,1);    //a合法 插入c
         int c=10000-a-b;
         ans=max(ans,t_find(0,c+1,1)); //定義任一個c值等價於一段(c,c+1)的單位長線段   
      }
    }   
 
    printf("%d\n",ans);
         
  }
  return 0;   
}

那個getn函式是拿來測試IO優化的加速有多少的
不過不知道是我寫的不好還是優化相對起來太渺茫了
和用scanf的時間完全一樣XDD
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組決賽
 NPSC 2008 高中組 決賽 E.不景氣的年代