교육 Codeforces Round 90 (Rated for Div. 2) F. Network Coverage (2 점 또는 사고)

F. Network Coverage
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The government of Berland decided to improve network coverage in his country. Berland has a unique structure: the capital in the center and nn cities in a circle around the capital. The capital already has a good network coverage (so the government ignores it), but the ii-th city contains aiai households that require a connection.
The government designed a plan to build nn network stations between all pairs of neighboring cities which will maintain connections only for these cities. In other words, the ii-th network station will provide service only for the ii-th and the (i+1)(i+1)-th city (the nn-th station is connected to the nn-th and the 11-st city).
All network stations have capacities: the ii-th station can provide the connection to at most bibi households.
Now the government asks you to check can the designed stations meet the needs of all cities or not — that is, is it possible to assign each household a network station so that each network station ii provides the connection to at most bibi households.
Input
The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.
The first line of each test case contains the single integer nn (2≤n≤1062≤n≤106) — the number of cities and stations.
The second line of each test case contains nn integers (1≤ai≤1091≤ai≤109) — the number of households in the ii-th city.
The third line of each test case contains nn integers (1≤bi≤1091≤bi≤109) — the capacities of the designed stations.
It's guaranteed that the sum of nn over test cases doesn't exceed 106106.
Output
For each test case, print YES, if the designed stations can meet the needs of all cities, or NO otherwise (case insensitive).
Example
input
Copy

5
3
2 3 4
3 3 3
3
3 3 3
2 3 4
4
2 3 4 5
3 7 2 2
4
4 5 2 3
2 3 2 7
2
1 1
10 10

output
Copy

YES
YES
NO
YES
YES

Note
In the first test case:

the first network station can provide 22 connections to the first city and 11 connection to the second city;

the second station can provide 22 connections to the second city and 11 connection to the third city;

the third station can provide 33 connections to the third city.

In the second test case:

the 11-st station can provide 22 connections to the 11-st city;

the 22-nd station can provide 33 connections to the 22-nd city;

the 33-rd station can provide 33 connections to the 33-rd city and 11 connection to the 11-st station.

In the third test case, the fourth city needs 55 connections, but the third and the fourth station has 44 connections in total.
제목:
n (< = 1e6) 개 도 시 는 하나의 고 리 를 구성 하고 도시 마다 인구 a [i] (< = 1e9), 용량 b [i] (< = 1e9) 가 있 으 며 i 번 째 도시 의 사람 은 i - 1 또는 i 번 째 도시 에 남아 모든 도시 의 인구 가 그 용량 을 초과 하지 않 고 YES 를 수출 할 수 있 는 지 물 어 볼 수 있다. 그렇지 않 으 면 NO.
사고: 두 가지 방법 이 있 는데 첫 번 째 방법 은 비교적 직관 적 이 고 첫 번 째 도시 가 첫 번 째 도시 에 남 겨 준 사람의 용량 이다.그 다음 에 남 은 용량 은 i + 1 개 도시 의 사람 에 게 남 겨 두 었 다. 이런 식 으로 미 루 면 마지막 으로 n 개 도시 의 잉여 용량 과 첫 번 째 도시 가 남 긴 용량 이 a [1] 를 충분히 수용 할 수 있 는 지 판단 하고 가능 하 다 면 바로 YES 이다.그렇지 않 으 면 중간 에 한 도시 의 인구 가 부족 하면 우 리 는 첫 번 째 도시 가 첫 번 째 도시 에 남 겨 진 사람의 용량 을 줄 이 고 마지막 에 a [1] 가 수용 하지 못 하면 남 겨 진 용량 을 높 일 것 이다.시간 복잡 도 O (nlog (1e9))
두 번 째 방법 은 하나의 배열 pre [i] 를 열 어 i 도시 에 남 은 사람 이 i - 1 도시 에 남 은 사람 수 를 기록 하 는 것 이다. b [i] 는 현재 도시 의 잉여 용량 을 나타 낸다.
처음에 b [1] 을 모두 a [2] 에 남 겨 두 었 습 니 다. 중간 에 용량 이 부족 하면 no 입 니 다. 그렇지 않 으 면 n - 1 번 도시 부터 b [i - 1] + = min (b [i], pre [i]) (이 식 을 잘 생각 하 세 요).마지막 으로 b [1] + b [n] 가 a [1] 보다 큰 지 판단 하면 됩 니 다.시간 복잡 도 O (n)
코드 (2 점):

#include
#define ll long long
#define inf 0x3f3f3f3f
#define mst(head,x,n) memset(head+1,x,n*sizeof(head[0]))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int maxn=2e6+5;
//const double pi=acos(-1.0);
//const double eps=1e-9;
//const ll mo=1e9+7;
int n,m,k;
int a[maxn],c[maxn],b[maxn];
int ans,tmp,cnt;
int flag;
int d[maxn];
bool ok[maxn];
template 
inline void read(T &X){
    X=0;int w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    if(w) X=-X;
}
int jud(int x){
    int res=b[0]-x;
    rep(i,1,n-1){
        if(a[i]>res+b[i]) return 0;
        if(res>=a[i]) res=b[i];
        else res=b[i]-(a[i]-res);
    }
    if(res+x>=a[0]) return 1;
    return 2;
}
void solve(){
    rep(i,0,n-1) read(a[i]);
    rep(i,0,n-1) read(b[i]);
    int l=0,r=b[0];
    while(l<=r){
        int mid=(l+r)>>1;
        int ans=jud(mid);
        if(ans==1) {
            puts("YES");
            return ;
        }
        if(!ans) r=mid-1;
        else l=mid+1;
    }
    puts("NO");
}
int main(){
/*
#ifdef ONLINE_JUDGE
#else
    freopen("D:/Temp/in.txt", "r", stdin);
#endif
*/
    int T,cas=1;
    read(T);
    while(T--)
    {
        read(n);
        solve();
    }
    return 0;
}

코드 (pre 레코드):

#include
#define ll long long
#define inf 0x3f3f3f3f
#define mst(head,x,n) memset(head+1,x,n*sizeof(head[0]))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int maxn=2e6+5;
//const double pi=acos(-1.0);
//const double eps=1e-9;
//const ll mo=1e9+7;
int n,m,k;
ll a[maxn],c[maxn],b[maxn];
int ans,tmp,cnt;
int flag;
ll pre[maxn];
bool ok[maxn];
template 
inline void read(T &X){
    X=0;int w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    if(w) X=-X;
}
int solve(){
    read(n);
    rep(i,0,n-1) read(a[i]);
    rep(i,0,n-1) read(b[i]);
    rep(i,0,n-1){
        if(b[(i-1+n)%n]+b[i]=a[i]){
pre[i]=a[i];
b[i-1]-=a[i];
}
else {
pre[i]=b[i-1];
b[i-1]=0;
b[i]-=(a[i]-pre[i]);
if(b[i]<0) return 0;
}
}
dep(i,n-2,1){
b[i-1]+=min(pre[i],b[i]);
if(b[i-1]<0) return 0;
}
if(b[0]+b[n-1]>=a[0]) return 1;
return 0;
}
int main(){
/*
#ifdef ONLINE_JUDGE
#else
freopen("D:/Temp/in.txt", "r", stdin);
#endif
*/
int T,cas=1;
read(T);
while(T--)
{
if(solve()) puts("YES");
else puts("NO");
}
return 0;
}