C. Sort Zero
最开始写了个n2的 TLE了以后 不知道咋优化
只好观察性质 发现我们要维护一个后缀 很多人说要维护前缀 其实也就少跑了60ms 我们维护一个mp[]记录的是哪个数不合法了 然后后面维护后缀时细节有点多 就没啥了
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
const int M = 1<<10;
const int mod = 1e9+7;
#define int long long
#define endl '\n'
#define Endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
signed main(){
fast
int T;cin>>T;
while(T--){
int n;cin>>n;
vector<int>a(n+1);
map<int,int>mp;
int mx=0;
set<int>s;
for(int i=1;i<=n;i++){
cin>>a[i];
s.insert(a[i]);
if(a[i-1]!=a[i])mp[a[i]]++;
if(mp[a[i]]>=2){
mx=max(mx,i);
}
}
int cnt=1;
for(int i=n;i>=mx+1;i--){
if(i-1>0){
if(a[i]>a[i-1]&&mp[a[i-1]]<=1)cnt++;
else if(a[i]==a[i-1]&&mp[a[i-1]]<=1)continue;
else break;
}
}
if(mp[a[n]]>=2)cnt=0;
cout<<s.size()-cnt<<endl;
}
return ~~(0^_^0);
}
1712D - Empty Graph
看到最大最小值 我们考虑二分 要是我们check（mid）时 有a[i]<ans/2上取整 那比不可能使其存在 我们让他修改到1e9或者随便一个大于等于ans/2的值都可以
最后我们考虑k剩下多少 要是k剩下2那么一定可以让一对变成1e9其他都是合法的 自然return 1 k要是不剩 我们就要查看每对有没有大于ans的 有就return1
最后k要是剩下1 我们分情况讨论 要是k原本就是2以上的 那我们已经变了一个1e9了 那自然在其旁边变个1e9 就可以了 要是原本只有1 那我们必须check每个的最大值 让后看其最大值>=ans
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
const int M = 1<<10;
const int mod = 1e9+7;
#define int long long
#define endl '\n'
#define Endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int n,k;
vector<int>a;
bool check(int ans){
int res=0,mx=0;
auto b=a;
for(int i=0;i<n;i++){
if((ans+1)/2>b[i]){
b[i]=1e9;
res++;
}
}
int maxv=0;
for(int i=0;i<n;i++){
maxv=max(maxv,b[i]);
if(i<n-1)mx=max(mx,min(b[i],b[i+1]));
}
if(k>=res){
if(k==res){
return mx>=ans;
}else if(k==res+1){
if(k==1){
return maxv>=ans;
}else{
return true;
}
}else return true;
}else return false;
}
signed main(){
fast
int T;cin>>T;
while(T--){
cin>>n>>k;
a.clear();
for(int i=1;i<=n;i++){int x;cin>>x;a.push_back(x);}
int l=0,r=1e9;
while(l<r){
int mid=(l+r+1)/2;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
return ~~(0^_^0);
}
还有就是关于这道贪心的证明 我看很多人都没解释 我这里通俗解释一下啊 代码就不贴了
我们最大值来源有两个 一个是mn*2 来的 一个就是自身本来权重就大来的
我们贪心处理前k-1个 再枚举最后一个1e9放哪 可以抽象看成我们把一个1e9放在另一个1e9（其实是大于ans的就可以）旁边 然后我们就可以get一个mn*2
但是枚举这个确实包括了自身本来权重就大这个是为什么呢 换言之 为啥自身本来权重就大 要从小到大删 其实我写这段话的时候就清楚了 我们乱搞出来就是要删第k短的边
所以很多人写的题解是两部分 一步就是删第k短 另一个就是枚举另一个数该放在哪个大数旁边 让后get一个低保