該題其實只需要利用multiset維護一下就可以了。 根據題意， ?利用題目特點， 可以發現， 如果正著枚舉的話， 前面的對后面的會產生影響， ?但是， 如果我們倒著枚舉就可以避免這個情況。 所以我們不妨先記錄每個時間點釋放魔法的次數， 然后倒著枚舉， 這樣當前這個數的能力值就是v+res ? （res為當前附加的魔法值， 因為后面時間增加的魔法，對于前面時間也一定增加了）。 ? ?所以， 我們不妨將每個值放進multiset， 然后二分查找對方組里是否存在比當前數大的數。 ?復雜度O(n*log(n)) 細節參見代碼： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 50000 + 10; const int maxv = 1000000 + 10; int T,n,m,vis[maxv],b,time[maxn]; struct node { int id, v; node(int ii=0, int vv=0):id(ii), v(vv) {} }a[maxn]; multiset<int> g1, g2; int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); g1.clear(); g2.clear(); multiset<int> :: iterator it; memset(vis, 0, sizeof(vis)); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].id,&a[i].v); for(int i=0;i<m;i++) { scanf("%d",&b); vis[b]++; } int res = 0, ans = 0; for(int i=n;i>=1;i--) { res += vis[i]; if(a[i].id == 0) { g1.insert(a[i].v+res); it = g2.upper_bound(a[i].v+res); if(it != g2.end()) ++ans; } else { g2.insert(a[i].v+res); it = g1.upper_bound(a[i].v+res); if(it != g1.end()) ++ans; } } printf("%d\n",n-ans); } return 0; } ~~~