#32700: 上下限&時間複雜度


jojo20061222@gmail.com (海之音)

學校 : 不指定學校
編號 : 199764
來源 : [210.71.78.245]
最後登入時間 :
2023-05-30 11:05:47
a468. 12439 - February 29 -- UVa12439 | From: [210.71.78.245] | 發表日期 : 2022-10-28 10:40

這題其實麻煩在字串處理(((((

如果用Python處理起來就很簡單 C++我建議直接複製題目的陣列然後開一個month[]作為字典的功用,這樣題目輸入之後就可以用查詢字典的方式取得月份

 

接著是做法的部分,如果想要用O(n)下去跑是絕對會爆掉的不用我講

所以我就直接用數學的方法算,讓時間複雜度降成O(1)
*程式風格毒瘤注意*

#include <iostream>
#include <string>
using namespace std;
int up(int a,int n);//取得比a小的最大的n的倍數

int low(int a,int n);//取得比a大的最小的n的倍數
int arr_find(string a);//取得月份
string month[]= {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November","December"};//字典
int main(){
    int n;
    cin >> n;
    for (int i=0;i<n;i++){
        string m,d;
        int y;
        cin >> m >> d >> y;
        int ms=arr_find(m);
        int ys=y;
        cin >> m >> d >> y;
        int me=arr_find(m);
        int ye=y;
        int upper,lower;
        if (ms>2) lower=ys+1;
        else lower=ys;
        if (me>2) upper=ye;
        else if (me==2 && d=="29,") upper=ye;
        else upper=ye-1;
        int n4=(up(upper,4)-low(lower,4))/4+1;
        int n100=(up(upper,100)-low(lower,100))/100+1;
        int n400=(up(upper,400)-low(lower,400))/400+1;
        cout << "Case " << i+1 << ": " << n4-n100+n400 << endl;
    }
}
int arr_find(string a){
    for (int i =0;i<12;i++){
        if (month[i]==a) return i+1;
    }
    return -1;
}
int up(int a,int n){
    return (a-a%n);
}
int low(int a,int n){
    if (a%n==0) return a;
    if (a%n!=0) return a-a%n+n;
    return -1;
}

 
ZeroJudge Forum