Codeforces Round 988
(Div. 3)因为当天有点头疼，飞速过了ABC，D卡住了，就去睡觉了
后来发现做法南辕北辙了
题目链接：D.
Sharky Surfing
我的思路：
大致是从后往前扫，每次都要排序一次，然后选最优的
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
| #include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N = 2e5;
int n , m , L;
int l[N+10] , r[N+10];
int x[N+10] , v[N+10];
int tempque[N+10] , top = 0;
signed main()
{
// ios::sync_with_stdio( false );
int t;cin >> t;
while( t -- ){
cin >> n >> m >> L;
for(int i = 1;i <= n;i ++){
cin >> l[i] >> r[i];
}
for(int i = 1;i <= m;i ++){
cin >> x[i] >> v[i];
}
int jump_max = 0;
for(int i = 1;i <= m;i ++){
if( x[i] < l[n] ) jump_max += v[i];
}
int ans = 0;bool flag = 1;
for(int i = n,j = m;j >= 1;i --){
if( jump_max > r[i] - l[i] + 1 ){
top = 0;
while( x[j] > l[i] ){
j --;
}
while( x[j] > l[i-1] ){
tempque[++top] = v[j--];
}
if( top == 0 ) continue;
sort( tempque + 1 , tempque + top + 1 );
int k = 1;
cout << "jp: " << jump_max << endl;
while( jump_max - tempque[k] > r[i] - l[i] + 1 ){
cout << "del: " << jump_max << " " << tempque[k] << endl;
cout << "de2: " << i << " " << r[i] - l[i] + 1 << endl;
jump_max -= tempque[k++];
ans ++;
if( k == top ) break;
}cout << "K1: " << k << " " << top << endl;
while( k <= top ) jump_max -= tempque[k++];
for(int kk = 1;kk <= top;kk ++) tempque[kk] = 0;
}else{
cout << -1 << endl;
flag = 0;
break;
}
}if( flag ) cout << ans << endl;
// for(int j = 1;j <= m;j ++) tempque[j] = 0;
}
return 0;
}
|
后来第二个测试点的第一百多行wa了，我意识到做法假了，去看题解了
正解：正着扫，直接用堆存，贪心最大
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
| #include<iostream>
#include<queue>
#include<algorithm>
#define int long long
using namespace std;
priority_queue< int , vector< int > , less < int > > q;
const int N = 2e5;
int n , m , L;
int l[N+10] , r[N+10];
int x[N+10] , v[N+10];
signed main()
{
ios::sync_with_stdio( false );
int t;cin >> t;
while( t -- ){
cin >> n >> m >> L;
for(int i = 1;i <= n;i ++){
cin >> l[i] >> r[i];
}
for(int i = 1;i <= m;i ++){
cin >> x[i] >> v[i];
}
int ans = 0 , jump_range = 0;
int tool_top = 1;
for(int i = 1;i <= n;i ++){
while( l[i] > x[tool_top] && tool_top <= m ){
q.push(v[tool_top++]);
}
while( r[i] - l[i] + 1 > jump_range ){
if( q.empty() ) {
ans = -1;break;
}
jump_range += q.top();
q.pop();ans ++;
}if( ans == -1 ) break;
}while( !q.empty() ) q.pop();
cout << ans << endl;
}
return 0;
}
|
总结：
不要钻牛角尖；简单题想复杂了，可以先吃点东西~