CODE FESTIVAL 2015 予選A C - 8月31日
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time import numpy as np from numpy import linalg as LA # 時々使う # import numpy as np # from decimal import Decimal, ROUND_HALF_UP # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from collections import defaultdict, deque # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) MOD = 10 ** 9 + 7 # MOD = 998244353 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N, T = il() hw = [] bt = 0 for _ in range(N): a, b = il() bt += b hw.append((a-b, a, b)) if bt > T: print(-1) exit() hw.sort() ret = 0 for r, a, b in hw: if bt + (a - b) <= T: bt += a - b ret += 1 print(N-ret) if __name__ == '__main__': main()
考え方
まずは全ての回答を写す前提で考えます。
全ての回答を写した合計(B
の合計した値)がT
を上回っている場合には、
夏休み中に宿題を終わらせることができません。
全ての回答を写した合計(B
の合計した値)がT
を下回っている場合には、
また自力で回答をする余地が残されています。
自力で回答した場合、B
の合計からA-B
時間増えます。
つまり、A-B
が小さい順から問題を解くことによって、できるだけ多くの問題を自力で回答することが出来ます。