在每个数出现第二次时记录下来，然后在输出。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n;
int cnt[N],a[N],k=0;
signed main(){
cin>>n;
for(int i=1;i<=n*3;++i){
int x;
cin>>x;
cnt[x]++;
if(cnt[x]==2){
a[++k]=x;
}
}
for(int i=1;i<=n;++i){
cout<<a[i]<<" ";
}
return 0;
}
表示吃了第 道菜后中毒状态为 时的最大得分。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
int n;
int f[N][2];
signed main(){
cin>>n;
f[0][0]=f[0][1]=0;
for(int i=1;i<=n;++i){
int x,y;
cin>>x>>y;
if(x==0){
f[i][0]=max(f[i-1][0]+y,f[i-1][1]+y);
f[i][0]=max(f[i][0],f[i-1][0]);
f[i][1]=f[i-1][1];
}
else{
f[i][1]=f[i-1][0]+y;
f[i][1]=max(f[i-1][1],f[i][1]);
f[i][0]=f[i-1][0];
}
}
cout<<max(f[n][0],f[n][1])<<"\n";
return 0;
}
用 map<int,int> 统计每个数字出现次数。再维护迭代器指向分界。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int n,k,q;
int a[N];
map<int,int> mp;
signed main(){
cin>>n>>k>>q;
memset(a,0,sizeof a);
mp[0]=n;
auto it=mp.begin();
int cnt=0,ans=0;
while(q--){
int x,y;
cin>>x>>y;
int A=a[x];
a[x]=y;
if(A==y){
cout<<ans+(it->first)*(k-cnt)<<"\n";
}
else{
mp[A]--;
mp[y]++;
if(A<=it->first&&y > it->first){
cnt++;
ans+=y;
}
else if(A > it->first && y <= it->first){
cnt--;
ans-=A;
}
else if(A>it->first&&y>it->first){
ans+=(y-A);
}
if(mp[A]==0){
if(it->first == A){
if(it != mp.begin()){
it--;
}
else{
it++;
cnt-=it->second;
ans-=(it->first) * (it->second);
}
}
mp.erase(A);
}
while(cnt>=k){
it++;
cnt-=it->second;
ans-=(it->first)*(it->second);
}
while(cnt+it->second < k){
cnt+=it->second;
ans+=(it->first)*(it->second);
it--;
}
cout<<ans+(it->first)*(k-cnt)<<"\n";
}
}
return 0;
}
这是我刚开始用 set<int> 排序后再统计的代码。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int n,k,q,x,y;
multiset<int> s;
int a[N];
signed main(){
// freopen("hh.txt","w",stdout);
cin>>n>>k>>q;
s.clear();
for(int i=1;i<=q;++i){
cin>>x>>y;
if(s.find(a[x])!=s.end()){
s.erase(s.find(a[x]));
}
a[x]=y;
s.insert(y);
auto it=s.end();
auto iit=*s.begin();
int ans=0,si=s.size();
for(int j=0;j<k;++j){
it--;
ans+= *it;
if(it==s.begin()) break;
}
// for(auto j:s) cout<<j<<" ";
// cout<<"\n";
cout<<ans<<"\n";
}
return 0;
}
AC
TLE