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 Bu sualın kodu niyə belə olur?Azərbaycanca danış və kodun mənasını izah elə!#include <bits/stdc++.h>
using namespace std;
#define ll long long #define ld long double #define endl '\n' #define pb push_back #define speedyboy ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define all(x) x.begin() , x.end() #define F first #define S second #define pll pair<ll , ll> #define YES cout << "YES" << endl; #define NO cout << "NO" << endl;
ll i , j , k , ans; const ll sz = 5e5 + 5 , INF = 1e18 , MOD = 1e9 + 7; ll a[sz] , b[sz];
void solve(){ ll n , sum1 = 0 , sum2 = 0; cin >> n; for(i = 1 ; i <= n ; i++){ cin >> a[i] >> b[i]; sum1 += a[i]; sum2 += b[i]; } if(sum1 > 0 || sum2 < 0){ cout << "No" << endl; return; } cout << "Yes" << endl; ll sum = -sum1; for(i = 1 ; i <= n ; i++){ cout << a[i] + min(sum , b[i] - a[i]) << ' '; sum -= min(sum , b[i] - a[i]); } cout << endl; }
signed main(){ speedyboy; ll t = 1; //cin >> t; while(t--){ solve(); } }
- Assistant
Bu kod, verilmiş
Nsayı cütü(Li, Ri)üçün uyğun olanXardıcıllığının mövcudluğunu yoxlayır və əgər varsa, həmin ardıcıllığı çıxarır. Gəlin kodun hər bir hissəsini Azərbaycan dilində ətraflı şəkildə izah edək.Giriş və Başlanğıc
#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define endl '\n' #define pb push_back #define speedyboy ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define all(x) x.begin() , x.end() #define F first #define S second #define pll pair<ll , ll> #define YES cout << "YES" << endl; #define NO cout << "NO" << endl; ll i , j , k , ans; const ll sz = 5e5 + 5 , INF = 1e18 , MOD = 1e9 + 7; ll a[sz] , b[sz];- Kitabxanalar və Ad məkanı:
#include <bits/stdc++.h>bütün standart C++ kitabxanalarını daxildir.using namespace std;standart ad məkanını istifadə edir. - Makro Təyinatları: Qısa yazılış üçün müxtəlif
typedefvə#definedirektivləri istifadə olunur. Məsələn,lllong longtipinə qısaldılır. - Sabitlər və Qlobal Dəyişənlər:
szmassivlərin maksimum ölçüsünü müəyyən edir.avəbmassivləriLvəRdəyərlərini saxlamaq üçün istifadə olunur.
Həll Funksiyası
void solve(){ ll n , sum1 = 0 , sum2 = 0; cin >> n; for(i = 1 ; i <= n ; i++){ cin >> a[i] >> b[i]; sum1 += a[i]; sum2 += b[i]; } if(sum1 > 0 || sum2 < 0){ cout << "No" << endl; return; } cout << "Yes" << endl; ll sum = -sum1; for(i = 1 ; i <= n ; i++){ cout << a[i] + min(sum , b[i] - a[i]) << ' '; sum -= min(sum , b[i] - a[i]); } cout << endl; }-
Girişın Oxunması: İlk olaraq,
nsayını oxuyur. Daha sonrancüt (L[i],R[i]) dəyərlərini massivlərə (a[i],b[i]) daxil edir vəsum1cəmini bütünL[i]dəyərlərinin cəmi,sum2isəR[i]dəyərlərinin cəmini saxlayır. -
Mümkünlük Şərtləri:
- Əgər
sum1 > 0(yəni, bütünL[i]dəyərlərinin cəmi müsbətdirsə) və yasum2 < 0(bütünR[i]dəyərlərinin cəmi mənfidirsə), o zaman tələb olunan ardıcıllıq mümkün deyil və "No" çıxış edilir.
- Əgər
-
Ardıcıllığın Tapılması:
- Əgər şərt ödənilmirsə, o zaman "Yes" çıxış edilir.
sum = -sum1təyin edilir. Bu, tələb olunan ardıcıllığınL[i]dəyərlərindən maksimumsuməlavə etməsini təmin etmək üçündür.- Sonra hər bir
iüçün:a[i] + min(sum, b[i] - a[i])hesablanır və çap edilir. Buradamin(sum, b[i] - a[i])əlavə ediləcək maksimum miqdarı təyin edir ki,X[i]dəyəriR[i]limitini keçməsin və toplam 0 olma şərtini təmin etsin.sumdəyəri yenilənir:sum -= min(sum, b[i] - a[i]).
Əsas Funksiya
signed main(){ speedyboy; ll t = 1; //cin >> t; while(t--){ solve(); } }- Girişin Təkmilləşdirilməsi:
speedyboymakrosu ilə giriş və çıxış sürəti artırılır. - Test Halları:
tdəyişəni test halları sayını təyin edir. Buradat=1olaraq qaldırılıb, yəni bir test halda işləyir. Əgər çoxlu test halları varsa,cin >> t;sətirini aktivləşdirə bilərsiniz. - Həllin Çağırılması:
solve()funksiyası çağırılır və problemi həll edir.
Ümumilikdə
Bu kod, hər bir cüt
(L[i], R[i])üçün mümkün olanX[i]dəyərlərini tapmaq və onların cəminin 0 olmasını təmin etmək üçün hazırlanıb. Əvvəlcə ən kiçik mümkün dəyərləri (L[i]) götürür və əgər bunların cəmi artıq 0-dan böyükdürsə, həllin mümkün olmadığını bildirir. Əks halda, cəmi 0-a gətirmək üçün hərX[i]dəyərinə əlavə edə biləcəyi maksimum miqdarıR[i] - L[i]ilə məhdudlaşdıraraq artırır.Nümunə:
- Sample 1:
- Giriş:
3cüt,(3,5), (-4,1), (-2,3) - Çıxış:
Yesvə4 -3 -1kimi bir ardıcıllıq
- Giriş:
Bu ardıcıllıq
4 + (-3) + (-1) = 0və hərX[i]dəyəri müvafiqL[i]vəR[i]aralığında yerləşir. - Kitabxanalar və Ad məkanı: