CodeForces 159E
2024-09-30 21:03:21
题目大意:
给定一堆带颜色和高度的魔方
用两种颜色的魔方,一种颜色接一种颜色向上拼接搭建成一个高塔,求高塔的最长高度,以及将拼接的过程中对应的编号顺序输出
多种情况成立输出任意一种即可
这里首先要对颜色(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]来求最大值,中间找到最大值时,记录一些相关数据以便最后的输出
每次找的时候要写一个判断保证这个条件下所得到的两种魔方不为一个颜色
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int N = ; int a[N] , max_id[N] , sec_id[N]; //a[]保存离散化后的c struct Node{
int v , num;
}; vector<Node> vec[N];
#define ll long long
ll max_val[N] , sec_val[N] , sum[N]; struct Cube{
int c , s , num;
bool operator<(const Cube &m)const{
if(c == m.c) return s > m.s;
return c < m.c;
}
}cu[N]; int bin_search(int x , int k)
{
int l= , r = k-;
while(l<=r){
int m=(l+r)>>;
if(a[m] == x) return m;
else if(a[m]>x) r = m-;
else l = m+;
}
} int main()
{
// freopen("a.in" , "r" , stdin);
int n;
while(scanf("%d" , &n ) == )
{
for(int i= ; i<=n ; i++) vec[i].clear(); for(int i = ;i<n ; i++)
{
scanf("%d%d" , &cu[i].c , &cu[i].s);
cu[i].num = i+;
} sort(cu , cu+n);
int k = ;
a[k++] = cu[].c;
for(int i= ; i<n ; i++){
if(cu[i].c != cu[i-].c) a[k++] = cu[i].c;
} memset(sum , , sizeof(sum));
memset(max_val , , sizeof(max_val));
memset(sec_val , , sizeof(sec_val));
for(int i= ; i<n ; i++){
int index = bin_search(cu[i].c , k);
Node node;
node.num = cu[i].num , node.v = cu[i].s;
vec[index].push_back(node);
sum[index] = sum[index] + cu[i].s;
int len = vec[index].size();
if(max_val[len] < sum[index]){
sec_val[len] = max_val[len];
sec_id[len] = max_id[len]; max_val[len] = sum[index];
max_id[len] = index;
}
else if(sec_val[len] < sum[index]){
sec_val[len] = sum[index];
sec_id[len] = index;
}
}
// cout<<"test: "<<max_val[1]<<" index: "<<max_id[1]<<" "<<sec_id[1]<<endl;
int col1 , col2 , len1 , len2;
ll ans = ;
for(int len= ; len<=n ; len++){
if(max_val[len] && sec_val[len]){
if(max_id[len] != sec_id[len]){
if(ans < max_val[len]+sec_val[len]){
ans = max_val[len]+sec_val[len];
col1 = max_id[len];
col2 = sec_id[len];
len1 = len , len2 = len;
}
}
}
//长度不等的时候排除所有两种颜色一样的情况
if(max_val[len] && max_val[len+]){
if(max_id[len] != max_id[len+]){
if(ans < max_val[len]+max_val[len+]){
ans = max_val[len]+max_val[len+];
col1 = max_id[len];
col2 = max_id[len+];
len1 = len , len2 = len+;
}
}
}
if(sec_val[len] && max_val[len+]){
if(sec_id[len] != max_id[len+]){
if(ans < sec_val[len]+max_val[len+]){
ans = sec_val[len]+max_val[len+];
col1 = sec_id[len];
col2 = max_id[len+];
len1 = len , len2 = len+;
}
}
}
if(max_val[len] && sec_val[len+]){
if(max_id[len] != sec_id[len+]){
if(ans < max_val[len]+sec_val[len+]){
ans = max_val[len]+sec_val[len+];
col1 = max_id[len];
col2 = sec_id[len+];
len1 = len , len2 = len+;
}
}
}
} printf("%I64d\n%d\n" , ans , len1+len2);
printf("%d" , vec[col2][].num);
for(int i= ; i<len1 ; i++){
printf(" %d" , vec[col1][i].num);
if(i+<len2) printf(" %d" , vec[col2][i+].num);
}
puts("");
}
return ;
}
最新文章
- SQL Server:APPLY表运算符
- jQuery File Upload 单页面多实例的实现
- Linux 下多用户申请git公钥方法
- 【洛谷P2737】Beef McNuggets
- AChartEngine绘制图形
- 【BZOJ-2440】完全平方数 容斥原理 + 线性筛莫比乌斯反演函数 + 二分判定
- 【openGL】画圆
- struts2:遍历自定义字符串数组,遍历Action实例所引用对象中的数组
- BootStrap简介及应用要点
- bzoj2208 [Jsoi2010]连通数(scc+bitset)
- 解决yii框架,gii脚手架不能使用。
- ASP.NET根据当前时间获取,本周,本月,本季度等时间段
- 【.NET Core项目实战-统一认证平台】第十六章 网关篇-Ocelot集成RPC服务
- 【转】反编译D-Link路由器固件程序并发现后门
- linux 文件压缩与解压
- Java String str = new String(value)和String str = value区别
- 【转】EF 获取类的属性并排除特定属性(getType().GetProperties())
- VMware同时使用三种网络模式的虚拟机,测试连通性
- tomcat学习步骤,附带打破双亲委派模型企业应用实战
- (转)Debug Assertion Failed! Expression: _pFirstBlock == pHead