codeforces-Ed76-D

codeforces-Ed76-D

七月 08, 2020

D. Yet Another Monster Killing Problem

题意
有n个怪物每个怪物有ai攻击力
有m个勇者每个勇者有pi攻击力和si耐力
当且仅当pi>=ai时这个勇者才可击败怪物
一个勇者最多能战斗si次
消耗完si次或遇到打不过的一天结束
问最少几天打完所有怪物

先判断能否打败所有怪物
贪心关键：
建立一个hero[si]存耐力值大于等于si的攻击力最大的勇士
然后双指针遍历去一个连续区间len怪物攻击力最大值maxn假如hero[len]>=maxn那么可以继续寻找更长len是否满足
len大于最大勇士耐久或不满足等式时天数++
(原来想的是找到每种耐力值下最大攻击力的勇士但是还不够贪心)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# include <bits/stdc++.h>

 using namespace std;
 typedef long long ll;
 int mon[(int)2e5+5];
 int hero[(int)2e5+5];
 int main(){
    std::ios::sync_with_stdio(false);
    int t;cin>>t;
    while(t--){
        int n,maxm=0;cin>>n;
        for(int i=1;i<=n;i++){
            cin>>mon[i];hero[i]=0;
            maxm=max(maxm,mon[i]);
        }
        int m,maxs=0;cin>>m;
        for(int i=1;i<=m;i++){
            int p,s;cin>>p>>s;
            hero[s]=max(hero[s],p);maxs=max(maxs,s);
        }
        int maxp=hero[maxs];
        for(int i=maxs-1;i>0;i--){
            maxp=max(maxp,hero[i]);
            hero[i]=maxp;
        }
        if(maxp<maxm){
            cout<<-1<<endl;
            continue;
        }
        maxm=0;int cnt=0;
        for(int i=1,x=1;i<=n;i++){
            maxm=max(maxm,mon[i]);
            if(hero[x]>=maxm){
                x++;
                if(x>maxs||i==n)x=1,maxm=0,cnt++;
            }
            else {
                cnt++;x=1;i--;
                maxm=0;
            }
        }
        cout<<cnt<<endl;
    }
 }

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# include <bits/stdc++.h>

using namespace std;

const int N = int(2e5) + 99;

int t;
int n;
int a[N];
int m;
int p[N], s[N];
int bst[N];

int main() {	
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d", &n);
		for(int i = 0; i <= n; ++i) bst[i] = 0;
		for(int i = 0; i < n; ++i)
			scanf("%d", a + i);
		scanf("%d", &m);
		for(int i = 0; i < m; ++i){
			scanf("%d %d", p + i, s + i);
			bst[s[i]] = max(bst[s[i]], p[i]);
		}
		for(int i = n - 1; i >= 0; --i)
			bst[i] = max(bst[i], bst[i + 1]);	
		

		int pos = 0;
		int res = 0;
		bool ok = true;
		while(pos < n){
			++res;
			int npos = pos;
			int mx = 0;
			while(true){
				mx = max(mx, a[npos]);
				if(mx > bst[npos - pos + 1]) break;
				++npos;
			}

			if(pos == npos){
				ok = false;
				break;
			}
			pos = npos;
		}

		if(!ok) res = -1;
		printf("%d\n", res);
	}

	return 0;

}