---

#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int> a,pair<int,int> b)
{
return a.second+a.first<b.first+b.second;
}
int main()
{
int t,n,a,b,ans,h;
cin>>t;
while(t--)
{
cin>>n;
ans=0;h=0;
vector<pair<int,int>> v;
for(int i=0;i<n;i++)
{
cin>>a>>b;
pair<int,int> k;
k.first=a,k.second=b;
v.push_back(k);
}
sort(v.begin(),v.end(),cmp);
for(int i=0;i<n;i++)
{
if(h<=v[i].second)
{
ans++;h+=v[i].first;
}
}
cout<<ans<<endl;
}
}

不知為何錯

 

 

---

提供一組測資，討論看看

1

100

20 5

12 8

19 12

10 15

9 15

10 17

11 19

12 21

9 23

15 24

12 26

20 27

4 27

18 30

10 31

4 32

1 35

5 37

19 39

14 39

7 40

9 40

4 42

17 43

9 44

18 46

11 47

6 49

18 51

20 55

20 59

12 59

2 63

19 66

4 67

17 71

3 72

16 72

17 75

11 76

16 77

7 79

11 81

4 81

2 83

11 87

20 91

6 93

6 93

12 97

13 101

3 105

12 107

12 109

19 109

2 109

4 111

18 115

4 117

9 118

3 120

10 120

4 121

13 121

10 122

4 126

12 130

9 134

8 134

12 135

17 137

3 139

15 142

19 146

18 150

1 152

7 156

9 159

6 161

17 164

18 166

17 166

19 167

10 171

1 175

4 175

2 176

9 180

6 183

19 187

12 189

5 190

16 190

4 194

19 198

19 198

14 202

1 206

11 208

14 210

8 211

 

我的解有 41 個

0 - H=1   L=35   floor=0

1 - H=1   L=152   floor=1

2 - H=1   L=175   floor=2

3 - H=1   L=206   floor=3

4 - H=2   L=63   floor=4

5 - H=2   L=83   floor=6

6 - H=2   L=109   floor=8

7 - H=2   L=176   floor=10

8 - H=3   L=72   floor=12

9 - H=3   L=105   floor=15

10 - H=3   L=120   floor=18

11 - H=3   L=139   floor=21

12 - H=4   L=27   floor=24

13 - H=4   L=32   floor=28

14 - H=4   L=42   floor=32

15 - H=5   L=37   floor=36

16 - H=4   L=67   floor=41

17 - H=4   L=81   floor=45

18 - H=6   L=49   floor=49

19 - H=4   L=111   floor=55

20 - H=4   L=117   floor=59

21 - H=4   L=121   floor=63

22 - H=4   L=126   floor=67

23 - H=4   L=175   floor=71

24 - H=4   L=194   floor=75

25 - H=5   L=190   floor=79

26 - H=6   L=93   floor=84

27 - H=6   L=93   floor=90

28 - H=6   L=161   floor=96

29 - H=6   L=183   floor=102

30 - H=7   L=156   floor=108

31 - H=9   L=118   floor=115

32 - H=8   L=134   floor=124

33 - H=9   L=134   floor=132

34 - H=9   L=159   floor=141

35 - H=9   L=180   floor=150

36 - H=10   L=171   floor=159

37 - H=11   L=208   floor=169

38 - H=12   L=189   floor=180

39 - H=14   L=202   floor=192

40 - H=14   L=210   floor=206

共41個

 

---

(修正) 應該是 42 個

 

 

 

 

 

 

 

 1 ->  H=9   L=15   floor=0

 2 ->  H=9   L=23   floor=9

 3 ->  H=4   L=27   floor=18

 4 ->  H=4   L=32   floor=22

 5 ->  H=1   L=35   floor=26

 6 ->  H=5   L=37   floor=27

 7 ->  H=7   L=40   floor=32

 8 ->  H=4   L=42   floor=39

 9 ->  H=6   L=49   floor=43

10 ->  H=2   L=63   floor=49

11 ->  H=4   L=67   floor=51

12 ->  H=3   L=72   floor=55

13 ->  H=7   L=79   floor=58

14 ->  H=4   L=81   floor=65

15 ->  H=2   L=83   floor=69

16 ->  H=6   L=93   floor=71

17 ->  H=6   L=93   floor=77

18 ->  H=3   L=105   floor=83

19 ->  H=2   L=109   floor=86

20 ->  H=4   L=111   floor=88

21 ->  H=4   L=117   floor=92

22 ->  H=9   L=118   floor=96

23 ->  H=3   L=120   floor=105

24 ->  H=4   L=121   floor=108

25 ->  H=4   L=126   floor=112

26 ->  H=8   L=134   floor=116

27 ->  H=9   L=134   floor=124

28 ->  H=3   L=139   floor=133

29 ->  H=1   L=152   floor=136

30 ->  H=7   L=156   floor=137

31 ->  H=9   L=159   floor=144

32 ->  H=6   L=161   floor=153

33 ->  H=1   L=175   floor=159

34 ->  H=4   L=175   floor=160

35 ->  H=2   L=176   floor=164

36 ->  H=9   L=180   floor=166

37 ->  H=6   L=183   floor=175

38 ->  H=5   L=190   floor=181

39 ->  H=4   L=194   floor=186

40 ->  H=14   L=202   floor=190

41 ->  H=1   L=206   floor=204

42 ->  H=11   L=208   floor=205

共 42 個

(不是原始測資，如有錯誤，請告知)

 

 

---

thanks