Codeforces Round 1000 (Div. 2) B and C

B. Subsequence Update

链接：Problem - B - Codeforces

题意：给定一个数组 可以选择任意个元素 后对这些元素进行排序 问你给定一个区间 这个区间的最小值

算法：贪心 排序

思路：下标1到r的最小个（r-l+1）元素 或者 下标l到n的最小个（r-l+1）元素

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int Q = 1e5 + 9;
const ll MOD = 1e9 + 7;
ll a[Q],b[Q];
void solve(){ll n,l,r;cin>>n>>l>>r;for (ll i = 1; i <= n; i++){cin>>a[i];b[i]=a[i];}sort(a+1,a+1+r);sort(b+l,b+1+n);ll ans=0,ans2=0;for (ll i = 1; i <= r-l+1; i++){ans+=a[i];}for (ll i = l; i <= r; i++){ans2+=b[i];}cout<<min(ans,ans2)<<"\n";
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll _ = 1;cin>>_;while(_--){solve();}return 0;
}

C. Remove Exactly Two

链接：Problem - C - Codeforces

题意：给出一个树 删除两个节点 最多有多少个联通块

算法：贪心

思路：将节点 先按度排序 再按相邻节点与自己度相同的个数排序 删除最大的两个即可，为什么？因为若当前有四个度为3的节点 删除第一个后 将其他三个节点的度数减少了一个 导致第二次删除的度数只能为2

此图先删除1和先删除2 3 4的结果不同

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int Q = 2e5 + 9;
const ll MOD = 1e9 + 7;
set<ll> d[Q];
bool vis[Q];
ll t[Q];
struct cmp
{bool operator()(pair<pair<ll,ll>,ll> l,pair<pair<ll,ll>,ll> r){if(l.first.first==r.first.first) return l.first.second>r.first.second;return l.first.first<r.first.first;}
};
void solve(){ll n;cin>>n;ll ans=1;for (ll i = 1; i <= n; i++) d[i].clear(),vis[i]=false,t[i]=0;for (ll i = 1; i < n; i++){ll o,p;cin>>o>>p;d[o].insert(p);d[p].insert(o);}priority_queue<pair<pair<ll,ll>,ll>,vector<pair<pair<ll,ll>,ll>>,cmp> pq;for (ll i = 1; i <= n; i++){for(auto j:d[i]){if(d[j].size()==d[i].size()) t[i]++;}pq.push({{d[i].size(),t[i]},i});}auto o=pq.top();while(pq.size())pq.pop();ans+=o.first.first-1;for(auto i:d[o.second]){d[i].erase(o.second);}for (ll i = 1; i <= n; i++) t[i]=0;for (ll i = 1; i <= n; i++){if(i==o.second) continue;for(auto j:d[i]){if(d[j].size()==d[i].size()) t[i]++;}pq.push({{d[i].size(),t[i]},i});}ans+=pq.top().first.first-1;cout<<ans<<"\n";}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll _ = 1;cin>>_;while(_--){solve();}return 0;
}