Capacity of an aircraft is K, you have N people with weights Wi. Find minimum number of air-crafts to transport all these people.

n <= 10^5 and k <= 10^9

How to approach this problem.

# | User | Rating |
---|---|---|

1 | Benq | 3813 |

2 | tourist | 3768 |

3 | maroonrk | 3570 |

4 | Radewoosh | 3535 |

5 | fantasy | 3526 |

6 | jiangly | 3523 |

7 | Um_nik | 3522 |

8 | orzdevinwang | 3441 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

# | User | Contrib. |
---|---|---|

1 | awoo | 180 |

2 | -is-this-fft- | 178 |

3 | nor | 169 |

4 | Um_nik | 168 |

5 | SecondThread | 164 |

6 | maroonrk | 163 |

7 | adamant | 162 |

8 | kostka | 161 |

9 | YouKn0wWho | 158 |

10 | antontrygubO_o | 154 |

Capacity of an aircraft is K, you have N people with weights Wi. Find minimum number of air-crafts to transport all these people.

n <= 10^5 and k <= 10^9

How to approach this problem.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/01/2023 19:20:52 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I think this problem is worth 1 million dollars.

It is a variation of the NP-complete Bin Packing problem.

Thanks!

As long as $$$K \geq \max{W_i}$$$ you can use one aircraft and then come back for more people

that's brilliant, but what if it's a one time use aircraft ?