链表
数组模拟大法好啊 orz 前向星 + 数组下标搞得各种线段树什么得
邻值查找
STL嚎啊
#include <iostream>
#include <set>
using namespace std;
typedef pair<int, int> P;
const int maxn = 1e5 + 5;
#define int long long
struct node{
int v, id;
node(){}
node(int _v, int _id){
v = _v, id = _id;
}
bool operator < (const node & a) const {
return v < a.v || (v == a.v && id < a.id);
}
}a[maxn];
P ans[maxn];
set<node> S;
signed main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++ ){
cin >> a[i].v;
a[i].id = i;
S.insert(a[i]);
}
S.insert(node(-2e9, -1)), S.insert(node(2e9, -1));
for(int i = n; i >= 2; i --) {
auto p1 = S.lower_bound(a[i]);
auto p3 = p1;
p3++;
int cha = 2e9, pos;
if((*p3).id != -1) pos = (*p3).id, cha = abs((*p3).v - a[i].v);
auto p2 = p1;
p2--;
if((*p2).id != -1 && cha >= abs((*p2).v - a[i].v)) pos = (*p2).id, cha = abs((*p2).v - a[i].v);
ans[i] = P(cha, pos);
S.erase(p1);
}
for(int i = 2; i <= n; i ++) cout << ans[i].first << " " << ans[i].second << endl;
return 0;
}
yxc 老师 写的模拟链表解法
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;
const int N = 100010;
int n;
int l[N], r[N];
int p[N];
PII a[N], ans[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i].first;
a[i].second = i;
}
sort(a + 1, a + 1 + n);
a[0].first = -3e9, a[n + 1].first = 3e9;
for (int i = 1; i <= n; i ++ )
{
l[i] = i - 1, r[i] = i + 1;
p[a[i].second] = i;
}
for (int i = n; i > 1; i -- )
{
int j = p[i], left = l[j], right = r[j];
LL left_value = abs(a[left].first - a[j].first);
LL right_value = abs(a[right].first - a[j].first);
if (left_value <= right_value) ans[i] = {left_value, a[left].second};
else ans[i] = {right_value, a[right].second};
l[right] = left, r[left] = right;
}
for (int i = 2; i <= n; i ++ ) cout << ans[i].first << ' ' << ans[i].second << endl;
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/29173/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
堆
先上手写堆
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000+5;
int heap[maxn];
int siz=0;
void push(int x){
heap[++siz]=x;
int cnt=siz;
while(cnt>1){
int nxt=cnt>>1;
if(heap[cnt>>1]>heap[cnt]) swap(heap[cnt>>1],heap[cnt]);
else break;
cnt=nxt;
}
return ;
}
void pop(){
swap(heap[siz],heap[1]);
siz--;
int cnt=1;
while((cnt<<1) <= siz){
int nxt=cnt<<1;
if((nxt|1)<=siz&&heap[nxt|1]<heap[nxt]) nxt++;// 先换右 写的方便
if(heap[nxt]<heap[cnt]) swap(heap[cnt],heap[nxt]); // 反正左右都行时 随意换
else break;
cnt=nxt;
}
return ;
}
int top(){
return heap[1];
}
int n,m,cmd,x;
int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>cmd;
if(cmd==1){
cin>>x;
push(x);
}else if(cmd==2){
cout<<top()<<endl;
}else if(cmd==3){
pop();
}
}
return 0;
}
超市
贪心 优先队列模拟 放前d天的 不能就尽可能放val大的
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e6+5;
priority_queue<int,vector<int>,greater<int> > que;
struct node{
int val;
int d;
bool operator < (const node & a)const{
return d<a.d;
}
}a[maxn];
signed main() {
int n;
while(cin>>n){
int day;
for(int i=1;i<=n;i++){
cin>>a[i].val>>a[i].d;
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
day=a[i].d;
if(que.size()<day) que.push(a[i].val);
else{
if(que.top()<a[i].val){
que.pop();
que.push(a[i].val);
}
}
}
int ans=0;
while(!que.empty()){
ans+=que.top();
que.pop();
}
cout<<ans<<endl;
}
return 0;
}
Sequence
提前放进去第一层 然后每取一个 把它之后的再放入 就不MLE了
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
const int maxe=2e5+10;
int n,m,cnt;
int a[maxn],b[maxn];
struct node{
int sum,p1,p2;
bool operator < (node const & a)const {
return a.sum<sum;
}
};
priority_queue<node> que;
int main() {
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) {
cin>>b[i];
que.push(node{a[1]+b[i],1,i});
}
for(int i=1;i<=n;i++){
node p=que.top();
cout<<p.sum<<" ";
que.pop();
que.push(node{a[p.p1+1]+b[p.p2],p.p1+1,p.p2});
}
return 0;
}
数据备份
模拟链表 + 贪心
当选择了num[i]后，反悔了，反之选择选了num[i-1]和num[i+1]时，获利便增加了num[i-1]+num[i+1]-num[i]。所以当num[i]被选时，我们就可以删去num[i-1]和num[i+1]，即为其代表的vis数组打上标记并把num[i]改成num[i-1]+num[i+1]-num[i]，放进堆中，重新找最大的。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e6+5;
struct node {
int id,val;
bool operator < (const node & a)const {
return val>a.val;
}
};
priority_queue<node> que;
int a[maxn];
bool vis[maxn];
int l[maxn],r[maxn];
signed main() {
int n,k;
cin>>n>>k;
for(int i = 0; i < n; i ++ ) cin >> a[i];
for(int i = n - 1; i>=1; i -- ) a[i] -= a[i - 1];
for(int i=1; i<n; i++) l[i]=i-1,r[i]=i+1,que.push(node {i,a[i]});
l[0]=0,r[n-1]=n;
a[0]=a[n]=0x3f3f3f3f;
int ans=0;
for(int i=1; i<=k; i++) {
while(!que.empty()&&vis[que.top().id]) que.pop();
node t=que.top();
que.pop();
ans+=t.val;
vis[r[t.id]]=vis[l[t.id]]=1;
a[t.id]=a[l[t.id]]+a[r[t.id]]-a[t.id];
l[t.id]=l[l[t.id]];
r[t.id]=r[r[t.id]];
l[r[t.id]]=t.id;
r[l[t.id]]=t.id;
que.push(node {t.id,a[t.id]});
}
cout<<ans<<endl;
return 0;
}
Huffman树 贪心
荷马史诗
每次都是将k个节点合并为1个（减少k-1个），一共要将n个节点合并为1个，如果（n-1）%（k-1）！=0 则最后一次合并时不足k个。也就表明了最靠近根节点的位置反而没有被排满，因此我们需要加入k-1-（n-1）%（k-1）个空节点使每次合并都够k个节点（也就是利用空节点将其余的节点挤到更优的位置上）。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5 ;
const int INF = 0x3f3f3f3f ;
struct node {
int w,h;
bool operator < (node const & a) const {
return a.w<w||(a.w==w&&a.h<h);
}
};
priority_queue<node> que;
signed main() {
int n,k,m;
cin>>n>>k;
int cnt=0;
if((n-1)%(k-1)) cnt+=(k-1)-(n-1)%(k-1);
for(int i=1; i<=cnt; i++) que.push(node {0,0});
cnt+=n;
for(int i=1; i<=n; i++) {
cin>>m;
que.push(node {m,0});
}
int ans=0;
while(que.size()>1) {
int res=0,hh=-1;
for(int i=0; i<k; i++) {
hh=max(que.top().h,hh);
res+=que.top().w;
que.pop();
}
ans+=res;
que.push(node {res,hh+1});
}
cout<<ans<<endl<<que.top().h<<endl;
return 0;
}
京公网安备 11010502036488号