题意：
给你n个关卡，每个关卡有一个怪物，怪物的攻击力为a【i】,你有n个英雄，每个英雄有一个攻击力，和疲劳值，只要英雄的攻击力比怪物的高就算打过了，同时疲劳减一，一天只能出战一个英雄，一个英雄可以打好几关（只要在疲劳范围内），打不过的话英雄就结束今天的挑战，转到第二天。问最少需要出战多少英雄才能通过所有关卡。
思路：先用一个数组。跑出相同忍耐值时，攻击力越大。然后·跑出这个数组的后缀pre数组，pre数组的含义是：忍耐值一定，攻击力最大。然后通过O（n）的复杂度跑·怪物的数组。当怪物的a【i】值大于pre数组在上一天的攻击力时，进入下一天。【变相的二分】【题目比较难叙述QAQ】
代码：
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 #define int long long 6 const int N=22e4;int n; 7 int arr[N]; 8 int pre[N]; 9 int str[N]; 10 int slove(){ 11 int ans=1;//总天数 12 int last_time=-1; 13 int maxn=0; 14 for(int i=0;i<n;i++){ 15 maxn=max(maxn,arr[i]); 16 if(pre[i-last_time]<maxn){ 17 last_time=i-1; 18 ans++; 19 maxn=arr[i]; 20 } 21 if(pre[1]<arr[i]){ 22 return -1; 23 } 24 } 25 return ans; 26 } 27 signed main(){ 28 ios::sync_with_stdio(0); 29 int _; 30 cin>>_; 31 while(_--){ 32 cin>>n; 33 int maxn1=0,maxn2=0; 34 for(int i=0;i<=n+10;i++) 35 arr[i]=0,str[i]=0,pre[i]=0; 36 for(int i=0;i<n;i++){ 37 cin>>arr[i]; 38 maxn1=max(maxn1,arr[i]); 39 } 40 int m; 41 cin>>m; 42 for(int i=0;i<m;i++){ 43 int x,y; 44 cin>>x>>y; 45 maxn2=max(maxn2,x); 46 pre[y]=max(pre[y],x);//相同忍耐值时，攻击力越大 47 } 48 if(maxn1>maxn2){ 49 cout<<"-1"<<‘\n‘; 50 continue; 51 } 52 for(int i=n-1;i>0;i--){ 53 pre[i]=max(pre[i+1],pre[i]);// 54 } 55 cout<<slove()<<‘\n‘; 56 } 57 return 0; 58 }
Educational Codeforces Round 76 (Rated for Div. 2) D题
原文：https://www.cnblogs.com/pengge666/p/11856316.html