day1
P3620 [APIO/CTSC2007] 数据备份
不配评蓝，反悔贪心，随随便便就AC了
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
struct node
{int val , l , r;
}b[N];
struct nod
{int val , id;bool operator <(nod shu) const {return val > shu.val;}
};
bool vis[N];
int a[N];
priority_queue<nod> q;
int main()
{int n , k;cin >> n >> k;for(int i = 1;i <= n;i++){scanf("%d" , &a[i]);if(i == 1){continue;}else{b[i].val = a[i] - a[i - 1];}b[i].l = i - 1;b[i].r = i + 1;q.push({b[i].val , i}); }b[1].val = b[n + 1].val = 0x3f3f3f3f;int ans = 0;for(int i = 1;i <= k;i++){while(vis[q.top().id]){q.pop();}nod x = q.top();q.pop();ans += x.val;vis[b[x.id].l] = vis[b[x.id].r] = 1; b[x.id].val = b[b[x.id].l].val + b[b[x.id].r].val - b[x.id].val;q.push({b[x.id].val , x.id});b[x.id].l = b[b[x.id].l].l;b[x.id].r = b[b[x.id].r].r;b[b[x.id].l].r = x.id;b[b[x.id].r].l = x.id;}cout << ans << endl;return 0;
}
这里一定要注意标记，最开始没写，赛时挂了90分
P3243 [HNOI2015] 菜肴制作
这题比T1简单，但难证，所以花了2h，不过也顺理成章的AC了
题外话，这题我赛时没证出来，导致70pts,代码还没来得及补，明天再补吧