D. Doremy‘s Connecting Plan Codeforces Round 906 (Div. 2)

Problem - D - Codeforces

题目大意：有一个长度为n的数组a，同时有一个n个点的图，编号与数组的编号对应，初始没有边，如果当前连通块的中a[i]的和+某一个点a[j]>=连通块的一个点i*某一个点j*c，那么就可以连通i和j，问能否使所有点在一个连通块内。

2<=n<=2e5;0<=a[i]<=1e12

思路：令当前已有的一个连通块为s，我们要找一个点j和s连通，那么我么肯定选择连通块中编号最小的一个点i，使i*j*c最小，如果s内的和+a[j]>=i*j*c，i和j就可以连通，既然i*j*c已经小于等于当前连通块的和，那么对于小于j的所有编号i*j*c都一定小于等于。

那么既然要选最小的i，那么我们就令a[1]是最小的连通块，因为反正要所有点联通也要连1，那不如从1开始连，这样就从1到n遍历，检查符不符合连通条件，如果到n时也符合，那么就是能连通

#include <bits/stdc++.h>
//#include<__msvc_all_public_headers.hpp>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
const ll MOD = 1e9 + 7;
ll a[N];
int n;
void solve()
{ll c;cin >> n;cin >> c;for (ll i = 1; i <= n; i++){cin >> a[i];}int ma = 1;//最大的能联通的位置ll sum = a[1];//前缀和ll nsum = a[1];//当前连通块的和for (ll i = 2; i <= n; i++){sum += a[i];if (nsum + a[i] >= i * c){//满足连通条件nsum = sum;ma = i;}}cout << (ma == n ? "YES" : "NO") << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--){solve();}}