反悔贪心
2025-12-15 22:08:20
发布于：上海
小孩写着复习用的，别太较真。
有人类负能量输出，请注意避雷。
开始时间：2025/12/15 20:00
好的，那么从P14361【CSP-S2025】社团招新开始吧。
呜呜呜哇哇哇我恨啊。CSP-S你就这么对我。
写到一半，去看大牛的游记了。
然后对它有了初始印象：反悔贪心反悔贪心，其实是先贪心再反悔的。（或者是一般反悔一边贪心）
看看社团招新吧。
以前做过，有个大概印象。
新的一年，小L一共找收到了n个新成员（n为偶数）。
算法协会一共有三个部门。其中第i个成员对第j个部门的满意度为a[i][j]。
小L不希望一个部门的新成员过多。即分配方案中，不存在一个部门被分配多余n/2个新成员。
你需要帮小L求出，满足他要求的分配方案的满意度最大值。
那么初步构建一个思考：n=1e5。
啊啊啊啊T1肯定冲着正解去啊。
额然后还是多测试点，记得初始化哈。
1e5，适用于O(nlogn)或者O(n)。
想到二分，贪心，STL。
好，那就照着反悔贪心想（嘻嘻开挂。
根据我们的初印象，我们先考虑怎样贪心，再考虑怎样反悔。
那么这里的是照着什么样的方式贪（或者是贪什么）? A：希望让每个人都进入自己最想进入的社团，
从而使得满意值总和最大。
细节n/2。也就是说，按照理想化方式（所有人都能进自己最相进的社团），最多只有一个社团的人数会超过n/2.
好的，那么此时绝对贪心完毕，反悔开始。
Q：如何反悔？A：反悔时，你也要贪心地反悔。我想要在把人移除社团时，我的损失是最小化的。
那损失是什么？损失=max(我所有社团中的值)-我所有社团中满意度第二大的值。
哦这个就是损失。
那么整个题目的框架差不多构建出来了。
这里的贪心其实有两个部分：1.对“选”的贪 2.对“悔”的贪
——————————————————
负能量碎碎念，请自行避雷
我只能说我真的不会贪心。还得多练练练练练练。为什么场上没切出T1？怎么这么**……啊啊啊啊啊啊好崩溃。
不过我昨天又切蓝了你们知道吗？啊啊啊啊但是好累啊，等我以后上马上开聊，我的那个什么标语就要写“三年磨砺，举步维艰。”真的太累了啊啊啊啊啊啊啊。凭什么要我又要NOIP一又要whk前20%？
我又不是天才好烦。下周还要六级有病吧
————————————————————————————————————
呱呱的提醒：这里的反悔贪心似乎是特殊的，在呱呱的印象中，反悔贪心似乎是需要用到什么队列的。
然后我去搓代码了。
那啥这种满意值什么的计算有的时候要注意是不是有负数，有负数，比较变量初始值就不能是零。
放个代码（不要说什么太复杂，写代码只是为了证明我的思路是正确的）
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N][5];
typedef long long ll;
vector<int>v1;
vector<int>v2;
vector<int>v3;
int l[N];//简短记录
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
v1.clear();
v2.clear();
v3.clear();
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++){
cin>>a[i][j];
}
}
ll ans=0;
for(int i=1;i<=n;i++){
int ma=0;//最大的那个数是多少。
int b=0;//最大的那个数字的下表是多少
for(int j=1;j<=3;j++){
if(a[i][j]>ma){
ma=a[i][j];
b=j;
}
}
// cout<<"sss:"<<i<<" "<<ma<<" "<<b<<endl;
if(b==1)v1.push_back(i);
if(b==2)v2.push_back(i);
if(b==3)v3.push_back(i);
ans+=ma;
}
if(v1.size()>n/2){
int lm=0;//l数组的下标记录
for(int i=0;i<v1.size();i++){
l[++lm]=max(a[v1[i]][1],max(a[v1[i]][2],a[v1[i]][3]));
int z=a[v1[i]][1]+a[v1[i]][2]+a[v1[i]][3];
int ll=min(a[v1[i]][1],min(a[v1[i]][2],a[v1[i]][3]));
int c=l[lm];//存储一下l[lm]
l[lm]=c-(z-c-ll);
//cout<<v1[i]<<" "<<l[lm]<<endl;
}
sort(l+1,l+1+lm);
for(int i=1;i<=v1.size()-n/2;i++){
ans-=l[i];
}
}
if(v2.size()>n/2){
int lm=0;//l数组的下标记录
for(int i=0;i<v2.size();i++){
l[++lm]=max(a[v2[i]][1],max(a[v2[i]][2],a[v2[i]][3]));
int z=a[v2[i]][1]+a[v2[i]][2]+a[v2[i]][3];
int ll=min(a[v2[i]][1],min(a[v2[i]][2],a[v2[i]][3]));
int c=l[lm];//存储一下l[lm]
l[lm]=c-(z-c-ll);
}
sort(l+1,l+1+lm);
for(int i=1;i<=v2.size()-n/2;i++){
ans-=l[i];
}
}
if(v3.size()>n/2){
int lm=0;//l数组的下标记录
for(int i=0;i<v3.size();i++){
l[++lm]=max(a[v3[i]][1],max(a[v3[i]][2],a[v3[i]][3]));
int z=a[v3[i]][1]+a[v3[i]][2]+a[v3[i]][3];
int ll=min(a[v3[i]][1],min(a[v3[i]][2],a[v3[i]][3]));
int c=l[lm];//存储一下l[lm]
l[lm]=c-(z-c-ll);
}
sort(l+1,l+1+lm);
for(int i=1;i<=v3.size()-n/2;i++){
ans-=l[i];
}
}
cout<<ans<<endl;
}
return 0;
}
看看没做过的蓝P1484种树（其实大部分正规的反悔贪心都是蓝+，据说是因为你很难去想到这是一个反悔贪心）
C在一条直线上挖了n个坑。都可以种树。
不会在相邻的两个坑中种树。至多会中k颗树。
C能预知自己在某个坑种树的获利是多少（可能为负）。
请你算出最大获利
我大概知道怎么做。
不过有一个问题：：不会在相邻的两个坑中种树。“
这么以来，感觉有点DP。但是n=3e5直接给婉拒了。
欸不过我有一计：分别从i=1和i=2开始跑一边反悔贪心，那不就行啦！（但其实不太确定，可以试试看）
然后我就搓出了神奇代码:
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int a[N];
typedef long long ll;
std::priority_queue<int,std::vector<int>,std::greater<int> >pq;
int main(){
int n,k;
cin>>n>>k;
ll ans=0;
for(int i=1;i<=n;i++)cin>>a[i];
bool can=0;
for(int i=1;i<=n;i++){
if(pq.size()<k&&a[i]>0&&!can){
pq.push(a[i]);
can=1;
continue;
}else if(pq.top()<a[i]&&!can){
pq.pop();
pq.push(a[i]);
can=1;
continue;
}else if(pq.top()<a[i]&&pq.top()==a[i-1]){
pq.pop();
pq.push(a[i]);
can=1;
continue;
}
can=0;
}
while(!pq.empty()){
ans+=pq.top();
pq.pop();
}
ll ans1=0;
for(int i=2;i<=n;i++){
if(pq.size()<k&&a[i]>0&&!can){
pq.push(a[i]);
can=1;
continue;
}else if(pq.top()<a[i]&&!can){
pq.pop();
pq.push(a[i]);
can=1;
continue;
}else if(pq.top()<a[i]&&pq.top()==a[i-1]){
pq.pop();
pq.push(a[i]);
can=1;
continue;
}
can=0;
}
while(!pq.empty()){
ans1+=pq.top();
pq.pop();
}
cout<<max(ans,ans1);
return 0;
}
反正是错的，去看题解了。
妙啊妙啊妙啊妙啊妙啊妙啊妙啊妙啊妙
请看链接描述这个链接里的litc写的第一篇题解。
非常精妙的思路，与我的狗*形成鲜明的对比！
这个思路真的太妙！
写得太好了！
不过其实还可以进行一点点补充。
算了不补充了，我去搓代码了。
剩余待完善
结束时间：2025/12/16
这里空空如也
有帮助，赞一个