e579 - 10050 - Hartals

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在 N 天內，由於 P 個政黨的罷工造成的損失工作天數。每個政黨有一個罷工參數 h，表示他們連續兩次罷工間隔的天數。罷工只會在工作日（星期一到星期四）發生，星期五和星期六不允許罷工。模擬從星期天開始。

解題思路

這題的核心是模擬每個政黨的罷工日，並計算總共的損失工作天數。

1. 讀取 N 和 P。
2. 建立一個大小為 N 的布林陣列 D，初始化為 0。D[i] = 1 表示第 i 天有罷工。
3. 對於每個政黨的罷工參數 h，從 h 開始，以 h 為間隔，標記 D 陣列中對應的日期為 1。
4. 遍歷 D 陣列，計算星期一到星期四且 D[i] 為 1 的天數。
5. 輸出計算得到的損失工作天數。

複雜度分析

• 時間複雜度: O(N * P + N)。O(N * P) 是模擬每個政黨的罷工日，O(N) 是計算損失工作天數。
• 空間複雜度: O(N)。需要一個大小為 N 的陣列來儲存罷工日。

程式碼

#include <iostream>
using namespace std;
int main(){
	int N,ans=0,i,P;
	cin >> N;
	while(cin >> N >> P){
		ans=0;
		int D[N]={};
		for(int j=0; j<P; j++){
			cin >> i;
			for(int k=i-1;k<N;k+=i)
				D[k]=1;
		}
		for(i=0;i<N;i++){
			if(i%7!=6&&i%7!=5){
				if(D[i]==1)
					ans++;
			}
		}
		cout << ans << endl;
	}
}