首页 > 代码库 > CodeForces 159E
CodeForces 159E
题目大意：
给定一堆带颜色和高度的魔方
用两种颜色的魔方，一种颜色接一种颜色向上拼接搭建成一个高塔，求高塔的最长高度，以及将拼接的过程中对应的编号顺序输出
多种情况成立输出任意一种即可
这里首先要对颜色（c值）进行离散化，这样每种颜色都对应有一个编号
用一个响亮vec[i]来保存 编号 i 的颜色的高度值以及对应要输出时的序号 ， 高度值由大到小保存，这个可以在一开始的魔方排序给c离散化的时候做到
拼接可以是两种颜色各有 len 个 ， 或者一种为len ， 一种为len+1
那么利用一个数组max_val [len] , sec_val[len]保存有len个颜色相同的魔方所能构建的最大和次大值
那么同时也要建立max_id[len] , sec_id[len]表示len个颜色相同的魔方所能构建的最大和次大值时对应的 颜色离散化后的标号
每次不断往向量中加入一个魔方的情况，加的同时就可以对上述的4个数组进行更新，因为 s 由大到小排列，那么加的时候始终得到的是当前颜色这个长度所能达到的最大
这样就可以max_val [len] , sec_val[len]来求最大值，中间找到最大值时，记录一些相关数据以便最后的输出
每次找的时候要写一个判断保证这个条件下所得到的两种魔方不为一个颜色
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 #include <vector> 6 #include <algorithm> 7 using namespace std; 8 const int N = 100005; 9 10 int a[N] , max_id[N] , sec_id[N]; //a[]保存离散化后的c 11 12 struct Node{ 13 int v , num; 14 }; 15 16 vector<Node> vec[N]; 17 #define ll long long 18 ll max_val[N] , sec_val[N] , sum[N]; 19 20 struct Cube{ 21 int c , s , num; 22 bool operator<(const Cube &m)const{ 23 if(c == m.c) return s > m.s; 24 return c < m.c; 25 } 26 }cu[N]; 27 28 int bin_search(int x , int k) 29 { 30 int l=0 , r = k-1; 31 while(l<=r){ 32 int m=(l+r)>>1; 33 if(a[m] == x) return m; 34 else if(a[m]>x) r = m-1; 35 else l = m+1; 36 } 37 } 38 39 int main() 40 { 41 // freopen("a.in" , "r" , stdin); 42 int n; 43 while(scanf("%d" , &n ) == 1) 44 { 45 for(int i=0 ; i<=n ; i++) vec[i].clear(); 46 47 for(int i = 0 ;i<n ; i++) 48 { 49 scanf("%d%d" , &cu[i].c , &cu[i].s); 50 cu[i].num = i+1; 51 } 52 53 sort(cu , cu+n); 54 int k = 0; 55 a[k++] = cu[0].c; 56 for(int i=1 ; i<n ; i++){ 57 if(cu[i].c != cu[i-1].c) a[k++] = cu[i].c; 58 } 59 60 memset(sum , 0 , sizeof(sum)); 61 memset(max_val , 0 , sizeof(max_val)); 62 memset(sec_val , 0 , sizeof(sec_val)); 63 for(int i=0 ; i<n ; i++){ 64 int index = bin_search(cu[i].c , k); 65 Node node; 66 node.num = cu[i].num , node.v = cu[i].s; 67 vec[index].push_back(node); 68 sum[index] = sum[index] + cu[i].s; 69 int len = vec[index].size(); 70 if(max_val[len] < sum[index]){ 71 sec_val[len] = max_val[len]; 72 sec_id[len] = max_id[len]; 73 74 max_val[len] = sum[index]; 75 max_id[len] = index; 76 } 77 else if(sec_val[len] < sum[index]){ 78 sec_val[len] = sum[index]; 79 sec_id[len] = index; 80 } 81 } 82 // cout<<"test: "<<max_val[1]<<" index: "<<max_id[1]<<" "<<sec_id[1]<<endl; 83 int col1 , col2 , len1 , len2; 84 ll ans = 0; 85 for(int len=1 ; len<=n ; len++){ 86 if(max_val[len] && sec_val[len]){ 87 if(max_id[len] != sec_id[len]){ 88 if(ans < max_val[len]+sec_val[len]){ 89 ans = max_val[len]+sec_val[len]; 90 col1 = max_id[len]; 91 col2 = sec_id[len]; 92 len1 = len , len2 = len; 93 } 94 } 95 } 96 //长度不等的时候排除所有两种颜色一样的情况 97 if(max_val[len] && max_val[len+1]){ 98 if(max_id[len] != max_id[len+1]){ 99 if(ans < max_val[len]+max_val[len+1]){100 ans = max_val[len]+max_val[len+1];101 col1 = max_id[len];102 col2 = max_id[len+1];103 len1 = len , len2 = len+1;104 }105 }106 }107 if(sec_val[len] && max_val[len+1]){108 if(sec_id[len] != max_id[len+1]){109 if(ans < sec_val[len]+max_val[len+1]){110 ans = sec_val[len]+max_val[len+1];111 col1 = sec_id[len];112 col2 = max_id[len+1];113 len1 = len , len2 = len+1;114 }115 }116 }117 if(max_val[len] && sec_val[len+1]){118 if(max_id[len] != sec_id[len+1]){119 if(ans < max_val[len]+sec_val[len+1]){120 ans = max_val[len]+sec_val[len+1];121 col1 = max_id[len];122 col2 = sec_id[len+1];123 len1 = len , len2 = len+1;124 }125 }126 }127 }128 129 printf("%I64d\n%d\n" , ans , len1+len2);130 printf("%d" , vec[col2][0].num);131 for(int i=0 ; i<len1 ; i++){132 printf(" %d" , vec[col1][i].num);133 if(i+1<len2) printf(" %d" , vec[col2][i+1].num);134 }135 puts("");136 }137 return 0;138 }
CodeForces 159E
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。