广州网站seo招聘,软文营销方案,临沭有做网站的吗,备案号链接工信部网站题意看起来很清新#xff0c;代码实现也基本在入门难度#xff0c;但是为什么我不会#xff01; 另#xff1a;反悔贪心 detailssummary$\texttt{solution}$/summary/details P2672 [NOIP2015 普及组] 推销员 $\texttt{solution}$ 发现答案… 题意看起来很清新代码实现也基本在入门难度但是为什么我不会 另反悔贪心 detailssummary$\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.ay.a;return x.sy.s;
}
int main()
{nrd();for(int i1;in;i) t[i].srd();for(int i1;in;i) t[i].ard();sort(t1,tn1,cmp);for(int i1;in;i) sum[i]sum[i-1]t[i].a;for(int i1;in;i) smax[i]max(smax[i-1],t[i].s*2);for(int in;i1;i--) suf[i]max(suf[i1],t[i].s*2t[i].a);for(int i1;in;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_queuell,vectorll,lessll q;
struct Data { ll x,t; }a[Maxn];
bool cmp(Data x,Data y)
{if(x.x!y.x) return x.xy.x;else return x.ty.t;
}
int main()
{nrd(),mrd();for(int i1;in;i) a[i](Data){rd(),rd()};sort(a1,an1,cmp);for(int i1;in;i){Nowa[i].x-a[i-1].xa[i].t,exist,q.push(a[i].t);while(!q.empty() Nowm) Now-q.top(),q.pop(),exist--;ansmax(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{n1}{2}\right]\) 个元素分别可以获得的最大价值是多少。 $\texttt{solution}$ 反悔贪心经典题啦 用链表记录剩余元素的信息用堆维护当前最大值。 假如现在有 \(A,B,C\) 三个元素顺序排列我们选择最大值 \(B\)那么就将 \(A,B,C\) 都从序列中删除并将 \(AC-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.valy.val; }
}cur,vis;
priority_queueData q;
int main()
{nrd(),krd();for(ll i1;in;i) st[i]rd(),R[i]i1,L[i]i-1;for(ll i1;in;i) val[i]st[i1]-st[i],q.push((Data){val[i],i});n--;val[0]val[n1]inf;for(ll i1;ik;i){while(used[q.top().num]) q.pop();curq.top(),q.pop();anscur.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;
}
