【AcWing】第 62 場周賽【2022.07.30】

2022 年 7 月 31 日
筆記
acwing, 模擬

AcWing 4500. 三個元素

題目描述

給定一個長度為 $n$ 的數組 $r\_1,r\_2,…,r\_n$。

請你找到其中的三個元素 $r\_a,r\_b,r\_c$，使得 $r\_a < r\_b < r\_c$ 成立。

輸入格式

第一行包含整數 $n$。

第二行包含 $n$ 個整數 $r\_1,r\_2,…,r\_n$。

輸出格式

共一行，輸出 $a,b,c$。

注意，題目要求輸出的是元素的下標。

如果方案不唯一，輸出任意合理方案均可。

如果無解，則輸出 -1 -1 -1。

數據範圍

前三個測試點滿足 $ 3≤n≤10 $。
所有測試點滿足 $3≤n≤3000 $ ，$1≤ri≤109 $。

輸入樣例1：

6
3 1 4 1 5 9

輸出樣例1：

4 1 3

輸入樣例2：

5
1 1000000000 1 1000000000 1

輸出樣例2：

-1 -1 -1

輸入樣例3：

9
10 10 11 10 10 10 10 10 1

輸出樣例3：

9 8 3

演算法

找出最大值和最小值，然後for循環找出比最大值小的，比最小值大的值，

C++ 程式碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 3010;
int a[N];

int main()
{
    int n;
    cin >> n;
    
    int maxval = -2e9 , maxadd;
	int minval = 0x3f3f3f3f , minadd;
	 
    for(int i = 1;i <= n;i ++)
    {
    	cin >> a[i];
		
		if(a[i] > maxval)
		{
			maxval = a[i];
			maxadd = i; 
		}
		if(a[i] < minval)
		{
			minval = a[i];
			minadd = i;
		}
    }
    
    bool flag = false;
    int ans;

    	for(int i = 1;i <= n;i ++)
    	{
    		if(i == maxadd || i == minadd)
    			continue;
    		if(a[i] > minval && a[i] < maxval)
    		{
    			ans = i;
    			flag = true;
    			break;
			}
		}
	
    
    if(!flag || ans == 0)
    	cout << "-1 -1 -1" << endl;
    else
    	cout << minadd << " " << ans << " " << maxadd << endl;
    
    return 0;
}

4501. 收集卡牌【補】

題目描述

某乾脆麵廠商在每包面中都放置有一張武將卡。

武將卡共分為 $n$ 種，編號 $1 – n$。

當集齊 $1 – n$ 號武將卡各一張時，就可以拿它們去換大獎。

為了換大獎，李華先後購買了 $m$ 包該品牌的乾脆面。

其中第 $i$ 包面中包含的武將卡的編號為 $a\_i$。

每當買完一包面，得到該面贈送的武將卡後，李華都會審視一遍自己手中的全部卡牌。

如果此時自己現有的卡牌能夠湊齊全部武將卡，那麼他就會立即將每種武將卡都拿出一張，並將拿出的卡牌寄給廠商，用來換獎。

請你分析李華購買乾脆面的整個過程並計算購買完每一包面後，李華能否湊齊全部武將卡用來換獎。

注意，每次換獎都需要消耗卡牌，消耗掉的卡牌就不屬於他了。

輸入格式

第一行包含兩個整數 $n,m$。

第二行包含 $m$ 個整數 $a\_1,a\_2,…,a\_m$。

輸出格式

輸出一個長度為 $m$ 的 $01$ 字元串，如果買完第 $i$ 包面後，李華能夠湊齊全部武將卡用來換獎，則第 $i$ 位字元為 $1$，否則為 $0$。

數據範圍

前 $5$ 個測試點滿足 $ 1≤n,m≤20 $。
所有測試點滿足 $ 1≤n,m≤105 $，$ 1≤ai≤n $。

輸入樣例1：

3 11
2 3 1 2 2 2 3 2 2 3 1

輸出樣例1：

00100000001

輸入樣例2：

4 8
4 1 3 3 2 3 3 3

輸出樣例2：

00001000

演算法

模擬解決，但需要使用tot記錄總數，如果tot達到n時，可以兌換，否則不可以兌換，需要注意兌換後需要判斷哪些數–後會變成0，tot–

C++ 程式碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int cnt[N];

int main()
{
	int n , m;
	scanf("%d%d",&n,&m);
	
	int tot = 0;
	string s;
	while(m --)
	{
		int x;
		scanf("%d",&x);
		
		if(cnt[x] == 0)
			tot ++;
		
		cnt[x] ++;
		
		if(tot == n)
		{
			s += '1';
			for(int i = 1;i <= n;i ++)
				if(-- cnt[i] == 0)
					tot --;
		}
		else
			s += '0' ;
	}
	
	cout << s << endl;
	return 0;
}

Tags: acwing 模擬