[基本練習]OI練習題：燈 light

【題目描述】

在一條無限長的路上，有一排無限長的路燈，編號爲1，2，3，4，……。

每一盞燈只有兩種可能的狀態，開或者關。如果按一下某一盞燈的開關，那麼這盞燈的狀態將發生改變。如果原來是開，將變成關。如果原來是關，將變成開。

在剛開始的時候，所有的燈都是關的。

小明每次可以進行如下的操作：

指定兩個數，a，t（a爲實數，t爲正整數）。將編號爲[a]，[2*a]，[3*a]，……，[t*a]的燈的開關各按一次。其中[k]表示實數k的整數部分。

在小明進行了n次操作後，小明突然發現，這個時候只有一盞燈是開的，小明很想知道這盞燈的編號，可是這盞燈離小明太遠了，小明看不清編號是多少。

幸好，小明還記得之前的n次操作。於是小明找到了你，你能幫他計算出這盞開着的燈的編號嗎？

【輸入格式】

第一行一個正整數n，表示n次操作。

接下來有n行，每行兩個數，ai，ti。其中ai是實數，小數點後一定有6位，ti是正整數。

【輸出格式】

僅一個正整數，那盞開着的燈的編號。

【輸入樣例】

3

1.618034 13

2.618034 7

1.000000 21

【輸出樣例】

20

【數據規模】

記T=t1+t2+t3+……+tn。

對於30%的數據，滿足T<=1000

對於80%的數據，滿足T<=200000

對於100%的數據，滿足T<=2000000

對於100%的數據，滿足n<=5000，1<=ai<1000，1<=ti<=T

數據保證，在經過n次操作後，有且只有一盞燈是開的，不必判錯。

【分析】

這數據規模太坑人了！

其實測試數據中，燈的最大編號僅為20000000。

也就是說，開個20000001的布爾數組即可。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
bool flag[20000001]={false};
int Max=0;
int Min=0x7fffffff;
int N;

int QZ(int a,double b)
{
    double c=(double)(a);
    b=b*c;
    return (int)floor(b);
}

int main()
{
    freopen("light.in","r",stdin);
    freopen("light.out","w",stdout);
    cin>>N;
    int T;
    double B;
    int Tmp;
    for (int i=1;i<=N;i++)
    {
        cin>>B>>T;
        for (int j=1;j<=T;j++)
        {
            Tmp=QZ(j,B);
            if(Tmp<Min)
                Min=Tmp;
            if(Tmp>Max)
                Max=Tmp;
            flag[Tmp]=!flag[Tmp];
        }
    }
   
    for (int i=Min;i<=Max;i++)
    {
        if(flag[i])
        {
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}