Problem Statement You are given N N pairs of integers ( L 1 , R 1 ) , ( L 2 , R 2 ) , ……
- User
Problem Statement You are given N N pairs of integers ( L 1 , R 1 ) , ( L 2 , R 2 ) , … , ( L N , R N ) (L 1 ,R 1 ),(L 2 ,R 2 ),…,(L N ,R N ).
Determine whether there exists a sequence of N N integers X
( X 1 , X 2 , … , X N ) X=(X 1 ,X 2 ,…,X N ) that satisfies the following conditions, and print one such sequence if it exists.
L i ≤ X i ≤ R i L i ≤X i ≤R i for each i
1 , 2 , … , N i=1,2,…,N. ∑ i
1 N X i
0 i=1 ∑ N X i =0. Constraints 1 ≤ N ≤ 2 × 1 0 5 1≤N≤2×10 5
− 1 0 9 ≤ L i ≤ R i ≤ 1 0 9 −10 9 ≤L i ≤R i ≤10 9
All input values are integers. Input The input is given from Standard Input in the following format:
N N L 1 L 1
R 1 R 1
L 2 L 2
R 2 R 2
⋮ ⋮ L N L N
R N R N
Output If no solution exists, print No. Otherwise, print an integer sequence X X that satisfies the conditions in the following format:
Yes X 1 X 1
X 2 X 2
… … X N X N
If multiple solutions exist, any of them will be considered correct.
Sample 1 Inputcopy Outputcopy 3 3 5 -4 1 -2 3 Yes 4 -3 -1 The sequence X
( 4 , − 3 , − 1 ) X=(4,−3,−1) satisfies all the conditions. Other valid sequences include ( 3 , − 3 , 0 ) (3,−3,0) and ( 5 , − 4 , − 1 ) (5,−4,−1).
Sample 2 Inputcopy Outputcopy 3 1 2 1 2 1 2 No No sequence X X satisfies the conditions.
Sample 3 Inputcopy Outputcopy 6 -87 12 -60 -54 2 38 -76 6 87 96 -17 38 Yes -66 -57 31 -6 89 9 idea ver.Azərbaycanca danış.Kodu necə yazmaq olar?
- Assistant
Bu problemi həll etmək üçün aşağıdakı addımları izləyə bilərik:
Problemin Anlayışı
Verilmiş N ədəd interval arasından hər bir seçərək belə bir sıra yaratmaq istəyirik ki:
- Hər bir üçün şərti təmin olunsun.
- Bütün ların cəmi 0-ə bərabər olsun.
Həll Yolu
-
Minimum və Maksimum Cəmləri Tapmaq:
- İlk olaraq, hər bir intervallar üçün ən kiçik mümkün dəyəri () seçərək minimal cəmi hesablayırıq.
- Eyni şəkildə, ən böyük mümkün dəyəri () seçərək maksimal cəmi tapırıq.
-
Mümkünlüyü Yoxlamaq:
- Əgər və aralığında deyilsə, belə bir sıra mümkün deyil.
- Yəni, olmalıdır.
-
Qarışıq Sıra Yaratmaq:
- Əgər mümkünlük varsa, hər üçün ilkin olaraq seçirik.
- Daha sonra, -a çatmaq üçün lazım olan fərqi () tapırıq.
- Sıralı şəkildə hər bir -yə bu fərqi əlavə edirik, lakin sərhədini keçməməlidir.
- Beləliklə, hər üçün , burada əlavə edilən fərq -dir.
Kod Nümunəsi (C++ Dilində)
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector<pair<ll, ll>> intervals(N); ll S_min=0, S_max=0; for(int i=0;i<N;i++){ cin >> intervals[i].first >> intervals[i].second; S_min += intervals[i].first; S_max += intervals[i].second; } if(S_min > 0 || S_max < 0){ cout << "No"; return 0; } // Initialize X with L_i vector<ll> X(N); for(int i=0;i<N;i++) X[i] = intervals[i].first; ll delta = 0 - S_min; for(int i=0;i<N && delta > 0;i++){ ll add = min(delta, intervals[i].second - intervals[i].first); X[i] += add; delta -= add; } if(delta !=0){ // Not possible cout << "No"; return 0; } // Output cout << "Yes\n"; for(int i=0;i<N;i++) cout << X[i] << (i<N-1?" ":"\n"); }İzahı
-
Giriş Oxuma:
- İlk olaraq, N ədəd intervalı oxuyuruq və onların minimal və maksimal cəmlərini hesablayırıq.
-
Mümkünlüyün Yoxlanması:
- Əgər minimal cəm 0-dan böyükdürsə və ya maksimal cəm 0-dan kiçikdirsə, "No" çap edirik.
-
Sıra Yaradılması:
- Hər bir üçün əvvəlcə seçirik.
- Sonra, 0-a çatmaq üçün lazım olan fərqi tapırıq.
- Fərqi mümkün qədər artıraq, lakin sərhədini keçməməliyik.
-
Nəticənin Çap Edilməsi:
- Əgər fərq 0-a çatıbsa, "Yes" və ədədlərini çap edirik.
- Əks halda, yenə "No" çap edirik.
Mürəkkəbliyi
- Vaxt Mürəkkəbliyi: O(N), çünki bütün intervalları bir dəfə oxuyuruq və sonra bir dəfə onları keçiririk.
- Yaddaş Mürəkkəbliyi: O(N), əlavə olaraq bir sıra saxlamalıyıq.
Bu yanaşma böyük ölçülü verilənlər üçün effektivdir və verilən şərtləri təmin edən bir sıra tapmaq üçün optimal üsuldur.