2020牛客国庆集训派对day3

A Leftbest

#include <bits/stdc++.h> //#define int ll using namespace std; #pragma GCC optimize(2) //#define int ll typedef long long ll; set<int > a; void solve() { ll sum=0; int n; cin>>n; for (int i = 0; i < n; ++i) { int x; cin>>x; a.insert(x); auto u = a.upper_bound(x); if (u!=a.end()){ sum+=*u; } } cout<<sum; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _ = 1; //cin >> _; while (_--) { solve(); } return 0; }

F Points

#include <bits/stdc++.h> #define int ll using namespace std; #pragma GCC optimize(2) //#define int ll typedef long long ll; const int maxn=3e5+10; int a[maxn]; void solve() { int n; cin>>n; for (int i = 1; i < n; ++i) { int u,v; cin>>u>>v; a[u]++,a[v]++; } int sum=0; for (int j = 1; j < n+1; ++j) { if (a[j]==1) sum++; } cout<<sum; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _ = 1; //cin >> _; while (_--) { solve(); } return 0; }

J Flowers

#include <bits/stdc++.h> #define int ll using namespace std; #pragma GCC optimize(2) //#define int ll typedef long long ll; const int maxn=3e5+10; int a[maxn]; int n,m; bool check(int mid){ int sum=0; for (int i = 1; i <=n; ++i) { sum+=min(a[i],mid); } return mid*m<=sum; } void solve() { int sum=0,ans=0; cin>>n>>m; for (int i = 1; i <= n; ++i) { cin>>a[i],sum+=a[i]; } int l=0,r=sum/m; while (l<=r){ int mid = (l + r) >> 1; if (check(mid)) l=mid+1,ans=mid; else r=mid-1; } cout<<ans<<"\n"; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _ = 1; cin >> _; while (_--) { solve(); } return 0; }