CF1398A-Bad Triangle
题目:
题目描述:
You are given an array $ a_1, a_2, \dots , a_n $ , which is sorted in non-decreasing order ( $ a_i \le a_{i + 1}) $ .
Find three indices $ i $ , $ j $ , $ k $ such that $ 1 \le i < j < k \le n $ and it is impossible to construct a non-degenerate triangle (a triangle with nonzero area) having sides equal to $ a_i $ , $ a_j $ and $ a_k $ (for example it is possible to construct a non-degenerate triangle with sides $ 3 $ , $ 4 $ and $ 5 $ but impossible with sides $ 3 $ , $ 4 $ and $ 7 $ ). If it is impossible to find such triple, report it.
输入格式:
The first line contains one integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases.
The first line of each test case contains one integer $ n $ ( $ 3 \le n \le 5 \cdot 10^4 $ ) — the length of the array $ a $ .
The second line of each test case contains $ n $ integers $ a_1, a_2, \dots , a_n $ ( $ 1 \le a_i \le 10^9 $ ; $ a_{i - 1} \le a_i $ ) — the array $ a $ .
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .
输出格式:
For each test case print the answer to it in one line.
If there is a triple of indices $ i $ , $ j $ , $ k $ ( $ i < j < k $ ) such that it is impossible to construct a non-degenerate triangle having sides equal to $ a_i $ , $ a_j $ and $ a_k $ , print that three indices in ascending order. If there are multiple answers, print any of them.
Otherwise, print -1.
样例:
样例输入 1:
1
2
3
4
5
6
7
| 3
7
4 6 11 11 15 18 20
4
10 10 10 11
3
1 1 1000000000
|
样例输出 1:
思路:
实现:
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
| /*
*User: ybw051114
*Time: 2020.08.14 22:35:09
*/
#include <bits/stdc++.h>
using namespace std;
#ifndef use_ios11
#define use_ios11
using namespace std;
struct ins
{
int ans;
ins() { ans = 1; }
#define endl '\n'
void read()
{
}
void read1(char &s)
{
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
s = c;
if (c == EOF)
ans = 0;
}
void read1(string &s)
{
s = "";
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
for (; isprint(c) && c != ' ' && c != '\n' && c != '\t'; c = getchar())
s += c;
if (c == EOF)
ans = 0;
}
template <typename T>
void read1(T &n)
{
T x = 0;
int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
{
if (c == '-')
f = -1;
if (c == EOF)
{
ans = 0;
return;
}
}
for (; isdigit(c); c = getchar())
x = x * 10 + c - 48;
n = x * f;
if (c == EOF)
ans = 0;
if (c != '.')
return;
T l = 0.1;
while ((c = getchar()) <= '9' && c >= '0')
x = x + (c & 15) * l, l *= 0.1;
n = x * f;
if (c == EOF)
ans = 0;
}
void write() {}
void write1(string s)
{
int n = s.size();
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(const char *s)
{
int n = strlen(s);
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(char s) { putchar(s); }
void write1(float s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%df", x);
printf(y, s);
}
void write1(double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dlf", x);
printf(y, s);
}
void write1(long double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dLf", x);
printf(y, s);
}
template <typename T>
void write1(T n)
{
if (n < 0)
n = -n, putchar('-');
if (n > 9)
write1(n / 10);
putchar('0' + n % 10);
}
template <typename T>
friend ins operator>>(ins x, T &n);
template <typename T>
friend ins operator<<(ins x, T n);
operator bool() { return ans; }
};
template <typename T>
ins operator>>(ins x, T &n)
{
if (!x.ans)
return x;
x.read1(n);
return x;
}
template <typename T>
ins operator<<(ins x, T n)
{
x.write1(n);
return x;
}
ins yin;
ins yout;
#endif
int n;
int a[100001];
int main()
{
int TTT;
yin >> TTT;
while (TTT--)
{
yin >> n;
for (int i = 1; i <= n; i++)
yin >> a[i];
sort(a + 1, a + n + 1);
if (a[1] + a[2] <= a[n])
yout << 1 << " " << 2 << " " << n << endl;
else
yout << -1 << endl;
}
return 0;
}
|