UVa 10050 題解 — C++

此筆記為UVa 10050的題目詳解，包含解題思路、C++範例程式碼。

Hartals (ZeroJudge e579.)

題目

一個社會研究組織採用了一組簡單的參數來模擬我們國家政黨運作的行為。
參數之一是一個正整數h，h稱為罷會(hartal)參數，它表示同一個政黨連續兩次連續罷會的間隔天數。
儘管該參數有點過於簡單，但還是能用於預測政黨罷會造成的影響。

以下範例為您說明：
考慮現在有三個政黨。假設h1 = 3，h2 = 4，h3 = 8，其中hi是第i方的罷會參數。
現在，我們將模擬這三個方在N = 14天的罷會行為。
模擬的起始天一定是星期天，並假設在每週的假日(星期五和星期六)不會有任何罷會情形。

上面的模擬顯示，在14天內將會罷會5天(分別在第3、4、8、9和12天)。
第6天沒有罷會，因為它屬於假日(星期五)。由此可知我們在2週內損失了5個工作天。

在這個問題中，考慮到多個政黨的罷會參數和天數N，您的工作是計算出這N天內我們因為罷會損失多少工作天。

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

這一題我用一個陣列 days 儲存有罷會的日子，用 k 迴圈（

$k=k+hi$）遍歷在 N 天內該政黨罷會的日子，如果是假日（k % 7 == 6 或 k % 7 == 0）則直接忽略這天的罷會請求，否則如果 days[k] 還沒有政黨罷會的話就把 total + 1，最後得出的 total 就是損失的工作天。

範例程式碼

#include <iostream>
using namespace std;

int main()
{
    int i, j, k;
    int T;

    cin >> T;
    
    for (i=0;i<T;i++) {
    	int N, P, hi;
    	
    	cin >> N >> P;
    	
    	int days[N+1]={}, total = 0;
    	
    	for (j=0;j<P;j++) {
    		cin >> hi;
    		
    		for (k=hi;k<=N;k=k+hi) {
    			if (k % 7 == 6 || k % 7 == 0)
    				continue;
    			
    			if (days[k] == 0) {
    				total++;
    				days[k] = 1;
				}
			}
		}
		
		cout << total << endl;
	}
}

運行結果

AC (2ms, 336KB)

tags: CPE 1星

查看更多資訊請至：https://www.tseng-school.com/