NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2013高中組初賽
 pC.胖胖天大大薯

作者 主題: pC.胖胖天大大薯  (閱讀 1509 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
pC.胖胖天大大薯
« 於: 十二月 17, 2013, 02:37:36 pm »

先把這些數字從小排到大,
然後一個一個取,
如果出現過了, 就把它變成兩倍加到另一個空的佇列,
之後就從佇列跟這串數字找比較小的出來,
如果佇列的數字已經出現過, 則直接丟棄,
比較特別的是這串數字的第一個數字和佇列的一樣,
則是拿佇列的來處理, 而原本的數字變兩倍後再加到佇列的後面,
直到這串數字用完以及佇列也沒有數字為止,
就可以找到答案。

參考程式:
代碼: [選擇]
#include <iostream>
#include <algorithm>

using namespace std;

const int N=1000001, MAX=2000000001;
int a[N], b[N];

int main()
{
    int T, n, i, j, m, ans, now;
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (i=0; i<n; i++)
            cin >> a[i];
        sort(a, a+n);
        a[n]=MAX;
        b[0]=MAX;
        for (i=0, j=0, m=0, now=0, ans=0; i<n || j<m; )
        {
            if (a[i]<b[j])
            {
                if (a[i]>now)
                {
                    now=a[i];
                    ans++;
                }
                else
                {
                    b[m++]=a[i]*2;
                    b[m]=MAX;
                }
                i++;
            }
            else if (a[i]>b[j])
            {
                if (b[j]>now)
                {
                    now=b[j];
                    ans++;
                }
                j++;
            }
            else // a[i]==b[j]
            {
                b[m++]=a[i]*2;
                b[m]=MAX;
                if (b[j]>now)
                {
                    now=b[j];
                    ans++;
                }
                i++;
                j++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
記錄

xavier13540

  • 新手
  • *
  • 文章數: 7
    • 檢視個人資料
Re: pC.胖胖天大大薯
« 回覆 #1 於: 三月 09, 2014, 09:39:03 pm »

好set 不用嗎
基本上就是
1. 把數列由小到大
2. 如果這個數沒在set裡 加進去
    如果這個數的兩倍沒在set裡 也加進去
    否則當天就只好不吃薯條了
代碼: [選擇]
#include<stdio.h>
#include<algorithm>
#include<set>
#define N 100010
using namespace std;
int a[N];
set<int>s;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",a+i);
        sort(a+1,a+n+1);
        s.clear();
        for(int i=1;i<=n;i++){
            if(s.find(a[i])==s.end())s.insert(a[i]);
            else if(s.find(a[i]<<1)==s.end())s.insert(a[i]<<1);
        }
        printf("%d\n",s.size());
    }
    return 0;
}
« 上次編輯: 三月 18, 2014, 07:02:52 pm 由 xavier13540 »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2013高中組初賽
 pC.胖胖天大大薯