Educational Codeforces Round 114 (Rated for Div. 2)-C. Slay the Dragon

原题链接：Educational Codeforces Round 114 (Rated for Div. 2)-C. Slay the Dragon
算法：二分
思路：明显由于题中数据范围太大，我们一定要考虑优化时间复杂度，由二段性用二分，数据太大也要防止爆数据用long long，读入的时候cin太慢用scanf快。
具体看代码实现

#include 
using namespace std;
typedef long long LL;
const int N = 2e5+5;
LL c[N];int bsearch_1(int l,int r,LL x)
{while (l<r){int mid=l+1ll+r>>1;if (c[mid]<=x) l=mid;else r=mid-1;}return l;
}int bsearch_2(int l,int r,LL x)
{while (l<r){int mid=l+r>>1;if (c[mid]>=x) r=mid;else l=mid+1;}return l;
}
int main()
{int n; cin>>n;LL sum=0;for (int i=1;i<=n;i++) scanf("%lld",&c[i]),sum+=c[i];sort(c+1,c+n+1);int m; scanf("%d",&m);while (m--){LL a,b; scanf("%lld%lld",&a,&b);int l=bsearch_2(1,n,a);int r=bsearch_1(1,n,a);LL ans=0;if (c[l]==a||c[r]==a) ans=b-sum+c[l]<0?0:b-sum+c[l];else{LL ans1=(c[l]-a>0?0:fabs(c[l]-a))+(b-sum+c[l]<0?0:b-sum+c[l]);LL ans2=(c[r]-a<0?fabs(c[r]-a):0)+(b-sum+c[r]<0?0:b-sum+c[r]);ans=min(ans1,ans2);}printf("%lld\n",ans);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！