首页 > 代码库 > poj 3666 Making the Grade & zoj 3512 Financial Fraud 左偏树 or dp
poj 3666 Making the Grade & zoj 3512 Financial Fraud 左偏树 or dp
//poj 3666
//分析：只是在2005年集训队论文黄源河提到的题目上略微有一点点变化
1 #include"iostream" 2 #include"cstdio" 3 using namespace std; 4 const int maxn = 2100; 5 int v[maxn],l[maxn],r[maxn],d[maxn]; //节点信息 6 int N; 7 int tot,root[maxn],num_now[maxn],num_del[maxn]; //树根信息 8 9 __int64 abs(__int64 ans)10 {11 return ans<0?-ans:ans;12 }13 14 int Merge(int x,int y)15 {16 if(!x) //分治终点17 return y;18 if(!y)19 return x;20 if(v[x]<v[y])21 swap(x,y);22 r[x] = Merge(r[x],y); //用递归函数进行分治，注意返回值23 if(d[l[x]]<d[r[x]]) //回溯，维护数组l，r，d24 swap(l[x],r[x]);25 d[x] = d[r[x]]+1;26 return x; //返回根节点27 }28 29 __int64 solve()30 {31 int i,j,k;32 __int64 res = 0;33 tot = 0;34 for(i = 1; i<=N; ++i) { //将每个节点都处理成一个区间（左偏树），根节点保存这个区间的中位数信息35 root[++tot] = i; //树根信息初始化36 num_now[tot] = 1; //树根信息初始化37 num_del[tot] = 0; //树根信息初始化38 l[i] = r[i] = d[i] = 0; //节点信息初始化39 while(tot>1&&v[root[tot-1]]>v[root[tot]]) { //循环条件为：最后一个区间的中位数小于前一区间；循环槽作为区间合并，并维护树根信息40 root[tot-1] = Merge(root[tot-1],root[tot]); //注意Merge的返回值41 num_now[tot-1] += num_now[tot];42 num_del[tot-1] += num_del[tot];43 --tot;44 while(num_now[tot]>num_del[tot]+1) {45 --num_now[tot];46 ++num_del[tot];47 root[tot] = Merge(l[root[tot]],r[root[tot]]); //注意Merge的返回值48 }49 }50 }51 for(i = k = 1; i<=tot; ++i) {52 for(j = 1; j<=num_now[i]+num_del[i]; ++j,++k) {53 res += abs(v[k]-v[root[i]]);54 }55 }56 return res;57 }58 59 int main()60 {61 int i;62 __int64 res_1,res_2;63 scanf("%d",&N);64 for(i = 1; i<=N; ++i) {65 scanf("%d",&v[i]);66 }67 res_1 = solve();68 for(i = 1; i<=N; ++i) {69 v[i] *= -1;70 }71 res_2 = solve();72 printf("%I64d\n",res_1<res_2?res_1:res_2);73 return 0;74 }
//zoj 3512
//感觉poj 3666数据太弱就去zoj 找了一道看起来一样的题目去交了，不能用__int64 ce一发，没读题wa一发，没注意数据范围re一发，不能交%I64d又wa一发，第五发才ac......
1 #include"iostream" 2 #include"cstdio" 3 using namespace std; 4 const int maxn = 50100; 5 int v[maxn],l[maxn],r[maxn],d[maxn]; //节点信息 6 int N; 7 int tot,root[maxn],num_now[maxn],num_del[maxn]; //树根信息 8 9 long long abs(long long ans)10 {11 return ans<0?-ans:ans;12 }13 14 int Merge(int x,int y)15 {16 if(!x) //分治终点17 return y;18 if(!y)19 return x;20 if(v[x]<v[y])21 swap(x,y);22 r[x] = Merge(r[x],y); //用递归函数进行分治，注意返回值23 if(d[l[x]]<d[r[x]]) //回溯，维护数组l，r，d24 swap(l[x],r[x]);25 d[x] = d[r[x]]+1;26 return x; //返回根节点27 }28 29 long long solve()30 {31 int i,j,k;32 long long res = 0;33 tot = 0;34 for(i = 1; i<=N; ++i) { //将每个节点都处理成一个区间（左偏树），根节点保存这个区间的中位数信息35 root[++tot] = i; //树根信息初始化36 num_now[tot] = 1; //树根信息初始化37 num_del[tot] = 0; //树根信息初始化38 l[i] = r[i] = d[i] = 0; //节点信息初始化39 while(tot>1&&v[root[tot-1]]>v[root[tot]]) { //循环条件为：最后一个区间的中位数小于前一区间；循环槽作为区间合并，并维护树根信息40 root[tot-1] = Merge(root[tot-1],root[tot]); //注意Merge的返回值41 num_now[tot-1] += num_now[tot];42 num_del[tot-1] += num_del[tot];43 --tot;44 while(num_now[tot]>num_del[tot]+1) {45 --num_now[tot];46 ++num_del[tot];47 root[tot] = Merge(l[root[tot]],r[root[tot]]); //注意Merge的返回值48 }49 }50 }51 for(i = k = 1; i<=tot; ++i) {52 for(j = 1; j<=num_now[i]+num_del[i]; ++j,++k) {53 res += abs(v[k]-v[root[i]]);54 }55 }56 return res;57 }58 59 int main()60 {61 int i;62 long long res_1;63 while(scanf("%d",&N)&&N) {64 for(i = 1; i<=N; ++i) {65 scanf("%d",&v[i]);66 }67 res_1 = solve();68 printf("%lld\n",res_1);69 }70 return 0;71 }
//看了看别人的blog发现这题还能dp搞，先挖个坑随后再填...
poj 3666 Making the Grade & zoj 3512 Financial Fraud 左偏树 or dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。