題意
https://vjudge.net/problem/CodeForces-1257D
你需要操作m個英雄去打敗n只怪物，每個英雄的力量值為pi,可以打敗si只怪物；每只怪物的力量值為ai，
當新的一天開始時，你可以選擇其中1個英雄去打怪，若在之前已有k只怪物被打敗，這個英雄將挑戰第k+1只怪物，此時有兩種情況：
1.英雄力量≤怪物力量，則英雄撤退，這一天結束，
2.英雄力量＞怪物力量，怪物被打敗，繼續挑戰下一只怪物，當n只怪物全部被打敗，或該英雄已打敗的怪物數量=si時，這一天結束，
你的任務是計算出打敗所有怪物所需要的最小天數，
思路
最簡單的想法就是用si大的盡可能多打，
維護每個耐力值si對應的力量最大的英雄，因為相等耐力值情況下肯定是選力量最大的要好，
再維護上面陣列的后綴最大值，這個其實就是耐力值少的也可以（注意是可以！不是一定）用耐力值大的代替，比如對于耐力值i，i+1，如果i+1的力量大于i，那么完全可以用i+1代替i去打，因為耐力值比i大，
然后用雙指標求解，當前遍歷到第i個怪物，用j往右邊延伸，看最遠能打到哪個怪物，這里要實時記錄這一段怪物力量的最大值，如果v[j-i+1]>=mx （v是上述處理完后綴最大值后的陣列），那么就可以延伸，v[j-i+1]表示耐力值為j-i+1~n（這一段的耐力值大于mx的英雄都可以使用）的最大英雄力量值，
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
int a[N],v[N];
int main()
{
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
v[i]=0;
}
int m;
cin>>m;
for(int i=1;i<=m;i++)
{
int p,s;
cin>>p>>s;
v[s]=max(v[s],p);
}
for(int i=n-1;i>=1;i--)
{
v[i]=max(v[i],v[i+1]);
}
int i=1,j,ans=0,flag=0;
while(i<=n)
{
if(a[i]>v[1])
{
flag=1;
break;
}
j=i;
int mx=a[i];
while(j<=n&&v[j-i+1]>=mx)
{
j++;
mx=max(mx,a[j]);
}
ans++;
i=j;
// cout<<i<<" "<<ans<<endl;
}
if(flag)
cout<<-1<<endl;
else
cout<<ans<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/122725.html
標籤：其他
上一篇：TetraMax只能寫出S pattern卻寫不出S pattern
下一篇：圖-迪杰斯特拉演算法