51nod1331

核心思路

这道题有一些细节需要注意。

分为两类情况,一类是中间有一些不去两头将交换的,另一类是所有的都交换。有一些狼可以左右两个交换区都经过。然后还有一堆非常难调的细节,考场上没能写出来。

复杂度为 O(n3)O(n^3)

完整代码

参考这位博主

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

#define REP(i,e,s) for(register int i=e; i<=s; i++)
#define DREP(i,e,s) for(register int i=e; i>=s; i--)
#define DE(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG(a) DE("DEBUG: %d\n",a)
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
using namespace std;

int read() {
int x=0,f=1,ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}

const int MAXN=50+10,INF=0x3f3f3f3f;

struct edge {
int s,t;
} a[MAXN];

bool cmp1(edge a,edge b) {
return a.s<b.s;
}

bool cmp2(edge a,edge b) {
return a.t<b.t;
}

int n,l,ans;

void calc(int pos) {
sort(a+1,a+pos+1,cmp2);
sort(a+pos+1,a+n+1,cmp2);
int leng=0;
REP(i,1,pos) leng+=a[i].s+a[i].t;
REP(i,pos+1,n) leng+=l-a[i].s+l-a[i].t;
int sum1=0,sum2=0;

REP(i,pos+1,n) {
sum1=0;
REP(j,1,pos) if(a[j].t>=a[i].t) sum1+=2*(l-a[j].t);
ans=min(ans,leng+sum1+sum2);
sum2+=2*a[i].t;
}
}

bool pd(int l,int r,int _l,int _r) {
int n1=0,n2=INF;
REP(i,l,r) n1=max(n1,a[i].t);
REP(i,_l,_r) n2=min(n2,a[i].t);
return n1<n2;
}

int main() {
int t=read();
while(t--) {
ans=INF;
n=read(),l=read();
REP(i,1,n) a[i]=(edge){read(),read()};
REP(i,0,n) {
sort(a+1,a+1+n,cmp1);
calc(i);
}
sort(a+1,a+1+n,cmp1);
int si=0;
REP(i,0,n) {
si+=a[i].t+a[i].s;
if(pd(1,i,i+1,n)) {
int j=i+1,tot=0;
for(; j<=n; j++) if(!pd(i+1,j,j+1,n)) {break;}
// DE("%d\n",j);
REP(k,i+1,j-1) tot+=abs(a[k].t-a[k].s);
REP(k,j,n) tot+=l-a[k].s+l-a[k].t;
ans=min(ans,si+tot);
}
}

printf("%d\n",ans);
}
return 0;
}

评论