题意：给你一个n和k，再给你n个城市离原点的距离，让你找k对城市，使他们之间的距离和最小。
思路：因为取k对城市，k对城市肯定是互相相邻的且不能出现重复。把两两相邻的城市的距离求入a数组中，所以当你选了ai，你就不能选ai+1或ai-1，所以有两种情况，要么选ai，要么选ai+1和ai-1，要么都不选，所以可以贪心，贪最小的，然后再把a[i+1]+a[i-1]-a[i]放进数组继续求最小选择。所以要维护一个优先队列，然后又因为要标记ai+1和ai-1防止时间超限，所以要用链表。
#include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<vector> #define ll long long using namespace std; ll a[100010]; ll b[100010]; int pre[100010],nxt[100010]; bool del[100010]; struct cmp { bool operator()(int x,int y) { return a[x]>a[y]; } }; priority_queue<int,vector<int>,cmp>q; int main() { ll n,k; while(~scanf("%lld%lld",&n,&k)) { memset(b,0,sizeof(b)); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } for(int i=2;i<=n;i++) { a[i-1]=a[i]-a[i-1]; } n--; a[0]=0x3f3f3f3f; for(int i=1;i<=n;i++) { q.push(i); pre[i]=i-1,nxt[i]=i+1>n?0:i+1; } ll sum=0; while(k--) { int x=q.top(); q.pop(); while(del[x]) { x=q.top(); q.pop(); } sum+=a[x]; del[pre[x]]=1; del[nxt[x]]=1; a[x]=a[pre[x]]+a[nxt[x]]-a[x]; q.push(x); pre[x]=pre[pre[x]]; nxt[x]=nxt[nxt[x]]; nxt[pre[x]]=x; pre[nxt[x]]=x; } printf("%lld ",sum); } }