2 条题解

  • 3
    @ 2021-6-13 18:15:51

    考虑贪心。

    由于在选定区间后的数都要加上一个数 e|e|,那么很明显我们要让这个数 e|e| 尽量的小,由于是绝对值,所以若要取最小,则 ee 应当等于 00

    考虑到 kk=0,0k=kk \oplus k=0,0 \oplus k=k,因此我们可以考虑让 a=b=c=da=b=c=d。而这种情况,我们可以选择一个长度为 11 的区间 [i,i][i,i],这时候区间中的最大值、最小值、平均数和中位数(平均数和中位数均为下取整)都是 fif_i,即 a=b=c=d=fia=b=c=d=f_i,我们只用从这个 fif_i 入手即可。

    由于要最小值小于等于 ss,所以我们贪心选择数列中最小的数 fjf_j ,每次减去 mm。不难发现,最终的答案为 fjsm\lceil \dfrac{f_j-s}{m} \rceil

    两个坑点:

    1. 如果原数列中已经有一个小于等于 ss 的数则直接输出 00

    2. 如果 m=0m=0,则先看坑点 11,如果坑点 11 不满足则直接输出 Impossible!

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    long long T;
    int main(){
    	cin>>T;
    	while(T--){
    		long long n,m,k,s,minn=1e9;
    		long long a[100009];
    		cin>>n>>m>>k>>s;
    		for(int i=1;i<=n;i++){
    			cin>>a[i];
    			minn=min(minn,a[i]);
    		}
    		if (minn<=s) cout<<0<<endl;
    		else if(m==0) cout<<"Impossible!"<<endl;
    		else cout<<ceil(1.0*(minn-s)/m)<<endl;
    	}
    	return 0;
    }
    
    • 1
      @ 2023-3-25 17:36:45
      #include<bits/stdc++.h>
      using namespace std;
      long long T;
      int main(){
      	cin>>T;
      	while(T--){
      		long long n,m,k,s,minn=1e9;
      		long long a[100009];
      		cin>>n>>m>>k>>s;
      		for(int i=1;i<=n;i++){
      			cin>>a[i];
      			minn=min(minn,a[i]);
      		}
      		if (minn<=s) cout<<0<<endl;
      		else if(m==0) cout<<"Impossible!"<<endl;
      		else cout<<ceil(1.0*(minn-s)/m)<<endl;
      	}
      	return 0;
      }
      
      
      • 1

      信息

      ID
      142
      时间
      1000ms
      内存
      128MiB
      难度
      7
      标签
      递交数
      93
      已通过
      21
      上传者