7月11日 bc总结
A题：暴力替换p，然后贪心求最大字段和。贪心求最大字段和的方法居然忘了。。。
now每次加上a[i]，如果now>ans，更新ans；如果now<0，now=0.也就是L移到下一个区间。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<set> #include<map> #include<string> #include<math.h> #include<cctype> #define ll long long #define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) #define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t)) #define rep(i,a,b) for(int (i)=(a);(i)>=(b);(i)--) #define repp(i,a,b,t) for(int (i)=(a);(i)>=(b);(i)-=(t)) #define PII pair<int,int> #define fst first #define snd second #define MP make_pair #define PB push_back #define RI(x) scanf("%d",&(x)) #define RII(x,y) scanf("%d%d",&(x),&(y)) #define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z)) #define DRI(x) int (x);scanf("%d",&(x)) #define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y)) #define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d",&(x),&(y),&(z)) #define RS(x) scanf("%s",x) #define RSS(x,y) scanf("%s%s",x,y) #define DRS(x) char x[maxn];scanf("%s",x) #define DRSS(x,y) char x[maxn],y[maxn];scanf("%s%s",x,y) #define MS0(a) memset((a),0,sizeof((a))) #define MS1(a) memset((a),-1,sizeof((a))) #define MS(a,b) memset((a),(b),sizeof((a))) #define ALL(v) v.begin(),v.end() #define SZ(v) (int)(v).size() using namespace std; const int maxn=1000100; const int INF=(1<<29); const double EPS=0.0000000001; const double Pi=acos(-1.0); ll a[maxn],p; int n; int main() { DRI(T); while(T--){ scanf("%d%I64d",&n,&p); REP(i,1,n) scanf("%I64d",&a[i]); ll ans=-INF; REP(i,1,n){ ll t=a[i]; a[i]=p; ll now=0; REP(j,1,n){ now+=a[j]; if(now>ans) ans=now; if(now<0) now=0; } a[i]=t; } cout<<ans<<endl; } return 0; }
B题：给n个a[i]，m个b[j]；当a[i]>=b[j]时，可以用a[i]抵消b[i]，然后得分增加a[i]-b[i]。每个a[i]和b[j]只能用一次，求最大得分。
由于答案一定是k个a[i]抵消k个b[j]的，而且显然，一定是用最大的k个a[i]抵消k个最小的b[j].
因此，a[i]从大到小遍历，b[j]从小到大遍历，这样可以保证a[i]最大，b[j]最小，当a[i]<b[j]时，直接break。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<set> #include<map> #include<string> #include<math.h> #include<cctype> #define ll long long #define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) #define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t)) #define rep(i,a,b) for(int (i)=(a);(i)>=(b);(i)--) #define repp(i,a,b,t) for(int (i)=(a);(i)>=(b);(i)-=(t)) #define PII pair<int,int> #define fst first #define snd second #define MP make_pair #define PB push_back #define RI(x) scanf("%d",&(x)) #define RII(x,y) scanf("%d%d",&(x),&(y)) #define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z)) #define DRI(x) int (x);scanf("%d",&(x)) #define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y)) #define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d",&(x),&(y),&(z)) #define RS(x) scanf("%s",x) #define RSS(x,y) scanf("%s%s",x,y) #define DRS(x) char x[maxn];scanf("%s",x) #define DRSS(x,y) char x[maxn],y[maxn];scanf("%s%s",x,y) #define MS0(a) memset((a),0,sizeof((a))) #define MS1(a) memset((a),-1,sizeof((a))) #define MS(a,b) memset((a),(b),sizeof((a))) #define ALL(v) v.begin(),v.end() #define SZ(v) (int)(v).size() using namespace std; const int maxn=1000100; const int INF=(1<<29); const double EPS=0.0000000001; const double Pi=acos(-1.0); int n,m; vector<ll> A,B; ll a,b; int cmp(ll a,ll b) { return a>b; } int main() { DRI(T); while(T--){ RII(n,m); A.clear();B.clear(); REP(i,1,n) scanf("%I64d",&a),A.PB(a); REP(i,1,m) scanf("%I64d",&b),B.PB(b); sort(ALL(A),cmp); sort(ALL(B)); int ia=0,ib=0; ll ans=0; for(;ia<n&&ib<m;){ ll tmp=A[ia]-B[ib]; if(tmp>0) ans+=tmp,ia++,ib++; else break; } cout<<ans<<endl; } return 0; }