Codeforces Gym101097I:Sticks (思维)
2024-08-31 07:12:47
http://codeforces.com/gym/101097/attachments
题意:现在有k种颜色的木棍,每种颜色有ni根木棍,每根木棍有一个长度,问是否有三根木棍可以组成三角形,并且这三根木棍的颜色都不相同。
思路:忘了并不能直接枚举第i根,然后找i-1和i-2根,因为还有很多情况没考虑到。
可以用三个变量,分别存储当前最大的三种颜色的最大值,然后根据新进来的颜色进行判定,进行更新。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 5000010
#define INF 0x3f3f3f3f
struct node {
int id; LL val;
bool operator < (const node &rhs) const {
if(val != rhs.val) return val < rhs.val;
return id < rhs.id;
}
} ;
vector<LL> vec;
vector<node> p;
node a, b, c; int main() {
freopen("sticks.in", "r", stdin);
freopen("sticks.out", "w", stdout);
int k; scanf("%d", &k);
int cnt = ;
for(int i = ; i <= k; i++) {
int n; scanf("%d", &n);
vec.clear();
for(int j = ; j <= n; j++) {
LL x; scanf("%lld", &x);
vec.push_back(x);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for(int j = ; j < vec.size(); j++) p.push_back( (node) { i, vec[j] } );
}
sort(p.begin(), p.end());
bool flag = ;
// a = p[1]; b = p[0]; c.id = 0, c.val = 0;
for(int i = ; i < p.size() && !flag; i++) {
if(a.id == p[i].id) {
if(p[i].val < b.val + c.val) printf("%d %lld %d %lld %d %lld\n", p[i].id, p[i].val, b.id, b.val, c.id, c.val), flag = ;
a = p[i];
} else if(b.id == p[i].id) {
if(p[i].val < a.val + c.val) printf("%d %lld %d %lld %d %lld\n", p[i].id, p[i].val, a.id, a.val, c.id, c.val), flag = ;
b = a; a = p[i];
} else {
if(p[i].val < a.val + b.val) printf("%d %lld %d %lld %d %lld\n", p[i].id, p[i].val, a.id, a.val, b.id, b.val), flag = ;
c = b; b = a; a = p[i];
}
}
if(!flag) puts("NIE");
return ;
}
最新文章
- Apache Cordova开发Android应用程序——番外篇
- iOS:GCD理解1(同步-异步、串行-并行)
- Oracle中的CHR()函数与ASCII()函数
- 关于Docker目录挂载的总结
- 常见Xcode参数设置错误
- Hadoop笔记
- ThinkPHP之中的getField、Find、select、返回数据类型详解(ThinkPHP之中所有数据读取了)
- 结构体 typedef关键字
- 国内流行的两大开源.net微信公众平台SDK对比分析
- Arduino 跷跷板(2016-01-04)
- 在SSMS里查看TDS数据包内容
- 设计模式:空对象模式(Null Object Pattern)
- QList 排序
- 优先队列的二叉堆Java实现
- 手把手教你构建 Kubernetes 1.8 + Flannel 网络(一)
- Java经典编程题50道之三十五
- (贪心 线段不相交问题)codeVs 1214 线段覆盖
- 编程菜鸟的日记-初学尝试编程-C++ Primer Plus 第5章编程练习2
- loj 10004 智力大冲浪
- Mybatis批量更新和插入