人类智慧贪心

题意看起来很清新，代码实现也基本在入门难度，但是为什么我不会！

另：反悔贪心

<details>

<summary>$\texttt{solution}$</summary>

</details>

P2672 [NOIP2015 普及组] 推销员

$\texttt{solution}$

发现答案只可能是一下两种情况：

选择最大的 $x$ 个推销疲劳值。
选择最大的 $x-1$ 个推销疲劳值，并选择一个距离较远的。

至于为什么只选择 $x-1$ 个而不是 $x-2$ 或更少:

加入我们要将第 $x-1$ 大的换为更远的，完全可以用第 $x$ 大的而不是 $x-1$ ，显然这样减小的更少呀。

之后就做完了。

#define Maxn 100005
int n,ans;
int smax[Maxn],sum[Maxn],suf[Maxn];
struct Data { int s,a; }t[Maxn];
bool cmp(Data x,Data y)
{
	 if(x.a!=y.a) return x.a>y.a;
	 return x.s>y.s;
}
int main()
{
	 n=rd();
	 for(int i=1;i<=n;i++) t[i].s=rd();
	 for(int i=1;i<=n;i++) t[i].a=rd();
	 sort(t+1,t+n+1,cmp);
	 for(int i=1;i<=n;i++) sum[i]=sum[i-1]+t[i].a;
	 for(int i=1;i<=n;i++) smax[i]=max(smax[i-1],t[i].s*2);
	 for(int i=n;i>=1;i--) suf[i]=max(suf[i+1],t[i].s*2+t[i].a);
	 for(int i=1;i<=n;i++) printf("%d\n",max(sum[i]+smax[i],sum[i-1]+suf[i]));
	 return 0;
}

P2107 小Z的AK计划

maoweishou 在 AK 一条街上行走，每走一步都消耗 $1$ 单位的时间，每到达一个机房都可以花费 $t$ 的时间 AK，也可以直接路过。

求 maoweishou 最多能 AK 多少次？

$\texttt{solution}$

似乎真的只有入门难度？

直接排序后从前往后选取，若超过了就暴力去掉消耗最大的，一路上取 $\max$ 即可。

#define Maxn 100005
typedef long long ll;
int n,ans,exist;
ll m,Now;
priority_queue<ll,vector<ll>,less<ll> > q;
struct Data { ll x,t; }a[Maxn];
bool cmp(Data x,Data y)
{
	 if(x.x!=y.x) return x.x<y.x;
	 else return x.t<y.t;
}
int main()
{
	 n=rd(),m=rd();
	 for(int i=1;i<=n;i++) a[i]=(Data){rd(),rd()};
	 sort(a+1,a+n+1,cmp);
	 for(int i=1;i<=n;i++)
	 {
	 	 Now+=a[i].x-a[i-1].x+a[i].t,exist++,q.push(a[i].t);
	 	 while(!q.empty() && Now>m) Now-=q.top(),q.pop(),exist--;
	 	 ans=max(ans,exist);
	 }
	 printf("%d\n",ans);
	 return 0;
}

P4597 序列sequence

给定长度为 $n$ 的一个序列，每次操作可以把某个数 $+1$ 或 $-1$。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。

求最小操作次数。

$n\le 10^5$

$\texttt{solution}$

似乎 $n\le 5000$ 的 dp 比较显然，之后就不会了

咕咕咕

P4053 [JSOI2007]建筑抢修

有 $n$ 个坏掉的建筑，修理第 $i$ 个需要 $c_i$ 的时间，如果在 $t_i$ 之前还没有修好它，就会彻底损坏，无法修理。

求出最多能够修好多少个建筑？

$n\le 2\times 10^5$

$\texttt{solution}$

按照彻底摧毁的时间排序，从小到大考虑。

我们在堆中记下当答案为最终元素个数时，构成答案的元素最小的花费。

如果我们发现可以将当前元素加入堆中使答案增加，直接添加。

否则判断如果可以使答案实际消耗减少就替换消耗最大的。

#define Maxn 150005
typedef long long ll;
int n,exist,ans;
ll Now;
priority_queue<ll,vector<int>,less<int> > q;
struct Data { ll Cost,Time; }a[Maxn];
bool cmp(Data x,Data y)
{
	 if(x.Time!=y.Time) return x.Time<y.Time;
	 return x.Cost<y.Cost;
}
int main()
{
	 n=rd();
	 for(int i=1;i<=n;i++) a[i]=(Data){rd(),rd()};
	 sort(a+1,a+n+1,cmp);
	 for(int i=1;i<=n;i++)
	 {
	 	 if(Now+a[i].Cost>a[i].Time)
		 {
		 	 if(a[i].Cost<q.top())
		 	 	 Now-=q.top(),q.pop(),q.push(a[i].Cost),Now+=a[i].Cost;
		 }
	 	 else Now+=a[i].Cost,exist++,ans=max(ans,exist),q.push(a[i].Cost);
	 }
	 printf("%d\n",ans);
	 return 0;
}

P3620 [APIO/CTSC 2007] 数据备份

一个环（变式——一条链）上有 $n$ 个元素，要求选取的任意两个元素互不相邻，求选出 $k,k\in\left[1,\dfrac{n+1}{2}\right]$ 个元素分别可以获得的最大价值是多少。

$\texttt{solution}$

反悔贪心经典题啦

用链表记录剩余元素的信息，用堆维护当前最大值。

假如现在有 $A,B,C$ 三个元素顺序排列，我们选择最大值 $B$，那么就将 $A,B,C$ 都从序列中删除，并将 $A+C-B$ 加入。

这样可以保证我们的任意选择都可以被返回，且保证最优。

#define Maxn 500005
ll n,k,ans;
ll R[Maxn],L[Maxn],st[Maxn],val[Maxn];
bool used[Maxn];
struct Data
{
	 ll val,num;
	 bool friend operator < (Data x,Data y) { return x.val>y.val; }
}cur,vis;
priority_queue<Data> q;
int main()
{
	 n=rd(),k=rd();
	 for(ll i=1;i<=n;i++) st[i]=rd(),R[i]=i+1,L[i]=i-1;
	 for(ll i=1;i<n;i++) val[i]=st[i+1]-st[i],q.push((Data){val[i],i});
	 n--;
	 val[0]=val[n+1]=inf;
	 for(ll i=1;i<=k;i++)
	 {
	 	 while(used[q.top().num]) q.pop();
	 	 cur=q.top(),q.pop();
		 ans+=cur.val,val[cur.num]=val[R[cur.num]]+val[L[cur.num]]-val[cur.num];
	 	 q.push((Data){val[cur.num],cur.num}),used[L[cur.num]]=used[R[cur.num]]=true;
	 	 L[cur.num]=L[L[cur.num]],R[cur.num]=R[R[cur.num]];
	 	 R[L[cur.num]]=cur.num,L[R[cur.num]]=cur.num;
	 }
	 printf("%lld\n",ans);
     return 0;
}

CF865D Buy Low Sell High

已知接下来 $n$ 天的股票价格，每天你可以买进一股股票，卖出一股股票，或者什么也不做。$n$ 天之后你拥有的股票应为 $0$，当然，希望这 $n$ 天内能够赚足够多的钱。

$\texttt{solution}$

假设有一个股票交易在第 $l$ 天买入，在 $r$ 天卖出，那么我们同样可以理解为在 $l$ 天买入，在 $l+1$ 天卖出后又买入。

每天我们都查看是否可以卖出股票，可以便直接累加最大收益，并将今天的价格加回到队列中，这样可以保证每天的收益都是最大的。

// Author:A weak man named EricQian
#define Maxn 300005
typedef long long ll;
int n;
ll ans,a[Maxn];
priority_queue<ll,vector<ll>,greater<ll> >q;
int main()
{
	 n=rd();
	 for(int i=1;i<=n;i++) a[i]=rd();
	 for(int i=1;i<=n;i++)
	 {
	 	 if(!q.empty() && q.top()<a[i]) ans+=a[i]-q.top(),q.pop(),q.push(a[i]);
	 	 q.push(a[i]);
	 }
	 printf("%lld\n",ans);
	 return 0;
}

CF730I Olympiad in Programming and Sports

有 $n$ 个选手，每个人有信奥和体育两个特长值 $a_i,b_i$，要求选出信奥特长生至多 $p$ 人，体育特长生至多 $s$ 人，是的所有选出的人的特长值之和最大。

$n\le 10^5$

$\texttt{solution}~1$ 贪心

如果我们定下了信奥特长生，则体育特长生可以从剩下的直接选取最大的解决。

那么我们最开始先预定信奥最强的 $p$ 个人当特长生，可以证明这些人都不会被排出特长生名录之外。

因此我们可以进行以下操作 $s$ 次：

将一个体育较强的人改为体育特长生，并添加一个人为信奥特长生。
或直接添加一个体育特长生。

可以用三个优先对列维护以上操作。

// solution 1:贪心 
#define Maxn 3005
typedef long long ll;
int n,p,s,bel[Maxn];
ll ans;
struct Data{ int num,x,y; }a[Maxn];
struct Sub
{
	 int num; ll val;
	 bool friend operator < (Sub x,Sub y) { return x.val<y.val; }
};
priority_queue<Sub> qa,qb,qab;
bool cmp1(Data x,Data y){ return x.x>y.x; }
bool cmp2(Data x,Data y){ return x.num<y.num; }
inline void Insert(int x)
{
	 if(bel[x]==0) qa.push((Sub){x,a[x].x}),qb.push((Sub){x,a[x].y});
	 else if(bel[x]==1) qab.push((Sub){x,a[x].y-a[x].x});
}
int main()
{
	 n=rd(),p=rd(),s=rd();
	 for(int i=1;i<=n;i++) a[i].x=rd(),a[i].num=i;
	 for(int i=1;i<=n;i++) a[i].y=rd();
	 sort(a+1,a+n+1,cmp1);
	 for(int i=1;i<=p;i++) bel[a[i].num]=1,ans+=a[i].x;
	 sort(a+1,a+n+1,cmp2);
	 for(int i=1;i<=n;i++) Insert(i);
	 for(int i=1;i<=s;i++)
	 {
	 	 while(!qa.empty() && bel[qa.top().num]!=0) qa.pop();
	 	 while(!qb.empty() && bel[qb.top().num]!=0) qb.pop();
	 	 while(!qab.empty() && bel[qab.top().num]!=1) qab.pop();
	 	 int opt=0; ll maxx=0;
	 	 if(!qab.empty() && !qa.empty())
		  	 maxx=qab.top().val+qa.top().val,opt=1;
	 	 if(qb.top().val>maxx) maxx=qb.top().val,opt=2;
	 	 ans+=maxx;
	 	 if(opt==1)
	 	 	 bel[qab.top().num]=2,bel[qa.top().num]=1,Insert(qa.top().num);
	 	 else bel[qb.top().num]=2;
	 }
	 printf("%lld\n",ans);
	 for(int i=1;i<=n;i++) if(bel[i]==1) printf("%d ",i);
	 printf("\n");
	 for(int i=1;i<=n;i++) if(bel[i]==2) printf("%d ",i);
	 printf("\n");
	 return 0;
}

$\texttt{solution}~2$ 费用流

源点 $s$ 到每个点建一条流量为 $1$，费用为 $0$ 的边（每个人只能只能参加一种比赛）
建三个汇点，汇点 $t1$ 控制参加编程的，汇点 $t2$ 控制参加体育的，汇点 $t$ 控制参加 $t1$ 和 $t2$ 的总人数
每个人两种实力分别向 $t1$，$t2$ 建流量为 $1$，费用为负实力

然后就跑最小费用最大流啦

P2512 [HAOI2008]糖果传递

有 $n$ 个小朋友坐成一圈，每人有 $a_i$ 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 $1$。

$n\le 10^6$

$\texttt{solution}$

如果题目只是在链上，就变成了均分纸牌的问题，假设每个人现有纸牌数为 $a_i$，平均为 $ave$，$a_i-ave$ 前缀和为 $pre_i$，则答案为 $\sum{|pre_i|}$。

回到这道题上，发现最优解一定存在环上两个人之间不存在糖果传递，可以想到断环成链。

如果断掉环上第 $k$ 条边，则贡献依次为 $|pre_1-pre_k|,|pre_2-pre_k|\dots$。

这就是“仓库选址”问题啦！直接将 $k$ 定位所有 $pre$ 的中位数，求出答案即可。

$\texttt{code}$

int n;
ll ave,Now,sum,ans;
ll a[Maxn],c[Maxn];
bool cmp(int x,int y){ return x<y; }
int main()
{
	 n=rd();
	 for(int i=1;i<=n;i++) a[i]=rd(),sum+=a[i];
	 ave=sum/n;
	 for(int i=1;i<=n;i++) c[i]=c[i-1]+ave-a[i];
	 sort(c+1,c+n+1,cmp),Now=c[(n+1)/2];
	 for(int i=1;i<=n;i++) ans+=absll(c[i]-Now);
	 printf("%lld\n",ans);
	 return 0;
}