题目

3、Cleaner old horse（sweeper）–900
时间限制： | 空间限制：
题目描述：
有 个自然数 .
Find out how many times you have done it at least ,An operation includes the following steps：
1.选择两个整数 满足 ,且 ;
2.将 修改为 ;
3.将 修改为 .
共 组测试数据.
输入格式：
第一行仅有一个正整数 （ ）,表示测试数据的组数.
接下来有 组测试数据：
第一行有一个正整数 （ ,且所有测试数据中 之和不超过 ）;
第二行为 个整数 （ ）.
输出格式：
对于每组测试数据,输出一行一个整数,表示至少多少次操作（可以为0）.

思路

The idea is to build a bridge,0Use one to make up for it,All greater than0to add,第一个非0after counting0算作1去相加$搭桥$,不算最后一个.

重点

ans最大为2*10⁵*10⁹= 2 * 10¹⁴
要开long long

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=2e5+10;
int t,n;
ll ans;
int a[maxn];
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		ans=0;
		bool flag=false;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
    
			scanf("%d",&a[i]);
			if(i==n)break;
			if(a[i]){
    
				ans+=a[i];
				flag=true;
			}
			else {
    
				if(flag)ans++;
				else continue;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}