人类智慧贪心
题意看起来很清新，代码实现也基本在入门难度，但是为什么我不会！
另：反悔贪心
$\texttt{solution}$
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,less > q;
struct Data { ll x,t; }a[Maxn];
bool cmp(Data x,Data y)
{
if(x.x!=y.x) return x.xm) 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}$
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 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