从Ｃ题开始写好了
首先我们分析假如我们确定了要选择一个长度为ｎ的序列，该怎么计算代价
很明显 一个是算保留多少个 一个是算要加多少个，然后如果我们算完了选择长度ｎ－１的序列 那么更新答案的时候只需要看ｎ这个数字是否存在就可以了，然后更新一下删掉多少个数字
所以我们把原序列排序 然后枚举选长度为ｂ［ｉ］的排列 就可以每次ｏ（１）计算了 时间复杂度Ｏ（ｎ）
#include<bits/stdc++.h> using namespace std ; #define maxn 400100 #define int long long int read(){ int ans = 0 , f = 1 ; char ch = getchar() ; while ( !isdigit(ch) ){ if( ch == '-' ) f = -1 ; ch = getchar() ; } while ( isdigit(ch) ) ans = (ans * 10) + (ch ^ '0') , ch = getchar() ; return ans * f ; } int t , n , c , d ; int ans; int a[maxn] , b[maxn] ; signed main(){ t = read() ; while(t--){ n = read() , c = read() ,d = read() ; for(int i = 1 ; i <= n ; i++) a[i] = read() , b[i] = a[i] ; sort(b + 1 , b + 1 + n) ; int size = unique(b + 1 , b + 1 + n) - b - 1; ans = 99999999999999 ; int temp = 0 ; if(b[1] != 1) ans = n * c + d ; for(int i = 1 ; i <= size ; i++){ int sum = 0 ; temp += (b[i] - b[i - 1] - 1) * d ; sum = (n - i) * c + temp ; // printf("sunm : i : %lld %lld temp : %lld \n" , i , sum , temp) ; ans = min(ans , sum) ; } printf("%lld\n" , ans) ; } return 0 ; }
感觉题解其实写的非常明白 实际上这个题也很简单 考试的时候很快公式就推出来了 结果最后错在用了 ｃｅｉｌ（（Ｌ－ａ）／ （ａ － ｂ）） 可能精度会有点问题 最后爆在这里了 查了好久没查出来 警钟长鸣！！！
其实这个难就难在你可以证明暴力是对的
考虑从一个点出发可以到哪些点 我们可以用类似于ｂｆｓ的方式来完成 每次取一个最小的ａ值的可以便利的点，判断一下可不可以遍历即可
此时的复杂度是ｎｌｏｇｎ的 因为我们可以用一个堆来维护可能遍历的点的状态
所以最后，我们从每一个从ａ值为０，且没有被遍历过的点开始ｂｆｓ即可
所以我们现在需要考虑 一个点最多会被遍历多少次
假如现在有三个点 ａ ， ｂ ， ｃ ａ还连着很多边 ｃ也是
ａ点是之前已经遍历过的点 我们现在在ｃ点上 ｃ是我们第一次遍历的点
也就是说 之前从ａ那边开始遍历的时候 它遍历不过来 也就是没法到ｃ的位置 为什么 因为ｂ把它卡住了！
那么现在 假设我们从ｃ这边有这个能力遍历过去，也就是说 我们有能力打败这个ｃ 这意味着什么呢
意味从ｃ这边的已经打过的怪物数量已经大于ａ［ｂ］，也就是ｃ这边的点集的大小大于ａ【ｂ】
而且ａ这边的点集大小是小于ａ【ｂ】的 ， 因为ａ没打过去
所以最终ｃ这边的大小一定是ａ这边的大小的两倍 ，因为ｃ最后会把ａ这边也遍历一遍 点集的大小自然就扩大了
所以说，ａ每次被遍历的时候，新的点集的大小至少是翻倍的，所以ａ这个点最终会被遍历ｌｏｇｎ次
因此 总复杂度就是ｎ（ｌｏｇｎ）＾２的
#include<bits/stdc++.h> using namespace std ; #define maxn 400100 #define int long long int read(){ int ans = 0 , f = 1 ; char ch = getchar() ; while ( !isdigit(ch) ){ if( ch == '-' ) f = -1 ; ch = getchar() ; } while ( isdigit(ch) ) ans = (ans * 10) + (ch ^ '0') , ch = getchar() ; return ans * f ; } int t , n , m ; int a[maxn] ; #define pii pair<int,int> vector<int> G[maxn] ; int vis[maxn] ; set<pii> q ; bool check(int u){ q.clear() ; q.insert({a[u] , u}) ; int sum = 0 ; while(!q.empty()){ pii now = *q.begin() ; q.erase(q.begin()) ; if(now.first > sum){ return 0 ; } vis[now.second] = u ; sum++ ; for(int i = 0 ; i < G[now.second].size() ; i++){ int v = G[now.second][i] ; if(vis[v] < u) q.insert({a[v] , v}) ; } } return sum == n ; } signed main(){ t = read() ; while(t--){ n = read() , m = read() ; for(int i = 1 ; i <= n ; i++) G[i].clear() , a[i] = read() , vis[i] = 0; for(int i = 1 ; i <= m ; i++){ int u = read() , v = read(); G[u].push_back(v) ; G[v].push_back(u) ; } bool flag = 0 ; for(int i = 1 ; i <= n ; i++){ if(a[i] == 0 && vis[i] == 0){ if(check(i)){ flag = 1; break ; } } } if(flag == 1){ printf("yes\n") ; } else printf("no\n") ; } return 0 ; }