思路分析
贪心，因为\(chips\)只能左移到最近的空格子，所以其实只需要考虑在最长的以1开头和以1结尾的串内（记作\(s\)）移动即可（其他部分没用，不然只会做多余的移动）。
至于怎么移，可以想象把从第一个1串右端的所有1串保持成串的形式，轮流滚近第一个1串，恰好接上为止，可以证明，滚的次数恰好就是\(s\)内0的个数。 画个图比较好理解： 
不难发现：答案就是\(s\)中0的个数，可以多结合几个样例分析一下。
### 代码实现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
void solve(){
int n,l=MAXN,r,cnt=0;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
if(a[i]==1){
r=i;
l=min(l,i);
cnt++;
}
}
cout<<r-l+1-cnt<<"\n";
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
|
思路分析
贪心，很显然，肯定是需要先打举例我们最近的怪物，再打次近的怪物，依此类推，只要在其中，有一个怪物打不死，那么我们就输了。
所以这里可以用到前缀和，预处理出前\(i\)个最近的怪物们的总血量（记作\(pre[i]\)），如果在对应的这段时间内，（也就是\(abs(a[i].pos)\)），我们打出的子弹数\(k*abs(a[i].pos)<pre[i]\)，那么我们就输出\(NO\)直接判掉。
注意得先派个序，按距离从小到大，可以用结构体+\(cmp\)。 ### 代码实现
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e6+10;
struct node{
ll hp,pos;
};
bool cmp(node a,node b){
return abs(a.pos)<abs(b.pos);
}
void solve(){
ll n,k,ans=0;
cin>>n>>k;
vector<node> a(n);
for(int i=0;i<n;i++)cin>>a[i].hp;
for(int i=0;i<n;i++)cin>>a[i].pos;
sort(a.begin(),a.end(),cmp);
for(int i=0;i<n;i++){
ans+=a[i].hp;
if(ans>k*abs(a[i].pos)){
cout<<"NO\n";
return;
}
}
cout<<"YES\n";
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
|
思路分析
其实就是看能否根据给出的子数组，构造出一个好数组（被翻译坑了）。
怎么构造？？？总和相同，但是相同位置的元素不同，并且元素都大于0。
有一个比较容易实现的想法：就是在原有的基础上，部分元素加1，显然，有一些元素需要减少，但是又不能减太多（不然就小于0了）。
这其中就有一个比较特别的元素：1。1只能加，不能减，那么要加多少个1（记作\(x\)）就只能由其他非一元素（能够贡献的记作\(y\)）贡献了。
代码实现
可以用前缀和，预处理出在各个区间内1的个数，以及各个区间内非一元素的最大贡献。
这里有用到一些小技巧：可以先在输入\(a[i]\)时，将\(a[i]--\)，这样求出来\(sum[r]-sum[l-1]\)就是\(y\)了。 需要注意特判一下：如果\(l==r\)，那么我们就无法构造出好数组（很显然）。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e6+10;
void solve(){
ll n,q,l,r,tot;
cin>>n>>q;
vector<ll> a(n+1),cnt(n+1),sum(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]--;
sum[i]=sum[i-1]+a[i];
cnt[i]=cnt[i-1]+(a[i]==0);
}
while(q--){
cin>>l>>r;
ll x=cnt[r]-cnt[l-1];
ll y=sum[r]-sum[l-1];
if(l==r||x>y)cout<<"NO\n";
else cout<<"YES\n";
}
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
|
思路分析
分析题意，很容易想到\(i-nd\)史莱姆只能被左边的或者右边的吃掉，先分析左边的情况。
假设\(i\)（偷懒，其实是\(i-nd\)史莱姆，下面也一样）被左边的史莱姆吃掉，先做一些定义：
\(ans[i]\)：被吃掉的最小操作次数。
\(l[i]\)：第\(i\)个数字的上一个与\(a[i]\)不同的位置。 \(left\)：记录一个区间的左端点。
如果存在\(left\)，使得： 1、\([left,i-1]\)区间的和>\(ans[i]\)。 2、\([left,i-1]\)区间数字种类\(>=2\)（因为相同不能互相吞并，那么最少需两种大小不同的史莱姆）。
那么操作次数就是:\(i-left\)。
可以发现\(i-1\)其实是固定的（对于每一个\(i\)来说）,并且\(left\)越小，区间和越大，反之，区间和越小，所以想到可以用二分。
那么我们就需要用前缀和求出区间和，再用二分求出端点位置。
但是怎么判断\([left,i-1]\)区间数字种类\(>=2\)，这时候\(l[i]\)就派上用场了。
二分的左右端点分别为\(left\)（这里的\(left\)与上面的\(left\)无关，是完全不同的两个），\(right\)。中间值为\(mid\)。 如果\(mid>l[i-1]\)，那么第二个条件就不成立（此时区间数字种类只有1）.
基本上就分析完了，但是如果是右边怎么办，我们只需要将数组反转即可。
代码实现
一些细节可以看注释
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e6+10;
vector<ll> a(MAXN),pre(MAXN),l(MAXN),ans(MAXN),b(MAXN);
inline bool check(int x,int i){
if(x>l[i-1])return 0;
if(pre[i-1]-pre[x-1]>a[i])return 1;
else return 0;
}
inline void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
pre[i]=l[i]=0;
}
for(int i=1;i<=n;i++){
cin>>a[i];
b[n-i+1]=a[i];
ans[i]=1e9;
}
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+a[i];
if(a[i]==a[i-1])l[i]=l[i-1];
else l[i]=i-1;
}
for(int i=1;i<=n;i++){
if(a[i]<a[i-1]){
ans[i]=1;
continue;
}
ll left=1,right=i-1;
while(left+1<right){
ll mid=(left+right)/2;
if(check(mid,i))left=mid;
else right=mid;
}
if(check(right,i))ans[i]=min(ans[i],i-right);
else if(check(left,i))ans[i]=min(ans[i],i-left);
}
for(int i=1;i<=n;i++){
a[i]=b[i];
}
for(int i=1;i<=n;i++){
pre[i]=l[i]=0;
}
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+a[i];
if(a[i]==a[i-1])l[i]=l[i-1];
else l[i]=i-1;
}
for(int i=1;i<=n;i++){
if(a[i]<a[i-1]){
ans[n-i+1]=1;
continue;
}
ll left=1,right=i-1;
while(left+1<right){
ll mid=(left+right)/2;
if(check(mid,i))left=mid;
else right=mid;
}
if(check(right,i))ans[n-i+1]=min(ans[n-i+1],i-right);
else if(check(left,i))ans[n-i+1]=min(ans[n-i+1],i-left);
}
for(int i=1;i<=n;i++){
cout<<(ans[i]==1e9?-1:ans[i])<<" ";
}
cout<<"\n";
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
|
以后再补qwq
不难发现：答案就是\(s\)中0的个数，可以多结合几个样例分析一下。
### 代码实现