ABC 203 C - Friends and Travel costs
境界条件の $ 10^{100}にたどり着くかどうか？
最大で
10^9(所持金) ＋ 10^9(街で得られる最大の金額) * 2 * 10^5(補充できる街の数)
10^14ぐらいのオーダーなので、long longに収まることにきづけるかどうか
間違えたのは
qsortを使ってソートする時に中身がlong longなので単純な引き算でcompar関数をreturnすると正しくsortされない
ので、if文で1, -1, 0を返すようにすると良いっぽい
code: c.c
typedef struct s_ab
{
long long A;
long long B;
} t_ab;
int compar(const void *a, const void *b)
{
long long A = (*(t_ab*)a).A;
long long B = (*(t_ab*)b).A;
if (A > B)
return 1;
else if (A < B)
return -1;
else
return 0;
}
int main()
{
int N;
unsigned long long K;
scanf("%d", &N);
scanf("%lld", &K);
t_ab *AB;
AB = calloc(N, sizeof(t_ab));
for (int i = 0; i < N; i++)
{
}
qsort(AB, N, sizeof(t_ab), compar);
unsigned long long current = 0;
unsigned long long ans = 0;
for (int i = 0; i < N; i++)
{
unsigned long long distant;
distant = ABi.A - current; if (K < distant)
{
// この街にはたどり着けない
ans = current + K;
K = 0;
break;
}
else
{
}
}
if (K > 0)
{
ans = current + K;
}
printf("%lld\n", ans);
return (0);
}