题目链接：
http://codeforces.com/contest/1119/problem/B
题目思路：
比赛的时候这个题写了好久，主要是就想着按照俩个间距最小放一起，然后就想着放一个把前面的优化一次就写不出来
然后看了这个豁然开朗，排完序相邻的就是间距最小了，嗯，就是这样
代码：
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
| #include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
#include <string>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#define LL long long
using namespace std;
const int MAX = 10010;
const int INF = 0xfffffff;
const int MOD = 1;
int T,N,M;
vector<int> bottle;
int main()
{
cin >> N >> M;
int flag= 1;
for(int i = 0;i < N;i++)
{
int x;
int height = 0;
cin >> x;
bottle.push_back(x);
sort(bottle.begin(),bottle.end());
for(int i = bottle.size()-1;i >= 0;i -= 2)
{
if(i >= 1) height += max(bottle[i],bottle[i-1]);
else height += bottle[0];
}
if(height > M)
{
for(int j = i+1;j<N;j++)
{
int x;
cin >> x;
}
cout << i <<endl;
flag = 0;
break;
}
}
if(flag)cout << N << endl;
return 0;
}
|
题目链接：
http://codeforces.com/contest/1119/problem/E
题目思路：
这题吧比赛的时候因为B题做了好久其实就没怎么看，我也不知道会不会，啊哈哈哈
看了题解发现挺简单的吧，比D要简单
就是能构成三角形的只有三个相同边。或者是俩大一小（三个不同，俩小一大都可以证明不能构成三角形）
然后就是贪心吧，优先俩大一小，然后三边相同
题目代码：
MY：
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
| #include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAX = 1000010;
const int INF = 0xfffffff;
const int EPS = 0.0000001;
const int MOD = 1e9+7;
int T,N,M;
int main()
{
cin >> N;
LL ans = 0;
LL surplus = 0;
while(N--)
{
LL x;
cin >> x;
if(x >= 2)
{
if(surplus > 0)
{
LL k = x / 2;
if(k > surplus)
{
ans += surplus;
x -= 2 * surplus;
surplus = 0;
if(x >= 3)
{
ans += x / 3;
surplus += x % 3;
}
else
{
surplus += x;
}
}
else
{
surplus -= k;
ans += k;
if(x % 2 == 1) surplus += 1;
}
}
else
{
ans += x / 3;
surplus += x % 3;
}
}
else
{
surplus += x;
}
}
cout << ans << endl;
return 0;
}
|
Other：
这个好简洁呀，没那么分类，直接一次通式处理QAQ
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
| #include<bits/stdc++.h>
using namespace std;
const int MAX = 1000010;
const int INF = 0xfffffff;
const int EPS = 0.0000001;
const int MOD = 1e9+7;
int T,N,M;
int main()
{
cin >> N;
LL ans = 0;
LL surplus = 0;
while(N--)
{
LL x;
cin >> x;
LL k;
k = min(surplus,x/2);
ans += k;
surplus -= k;
x -= 2*k;
ans += x / 3;
surplus += x % 3;
}
cout << ans << endl;
return 0;
}
|
