SZU2

CF:Problem 425A

区间暴力，枚举区间。交换选定区间最小值和剩余区间最大值k次。

其实等同于将剩余区间最大k个加到选定区间里，然后排序

#include <iostream>

#include <string>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <cctype>

#include <vector>

#include <iterator>

#include <set>

#include <map>

#include <sstream>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))

#define pf printf

#define sf scanf

#define spf sprintf

#define pb push_back

#define debug printf("!\n")

#define INF 10000

#define MAXN 5010

#define MAX(a,b) a>b?a:b

#define blank pf("\n")

#define LL long long

#define ALL(x) x.begin(),x.end()

#define INS(x) inserter(x,x.begin())

#define pqueue priority_queue

int a[];

int n,k;

int main()

{

     int i,j,m;

     while(sf("%d%d",&n,&k)==)

     {

          for(i =;i<n;i++)

               sf("%d",&a[i]);

          int mx=-;

          for(i =;i<n;i++)

          {

               for(j =i;j<n;j++)

               {

                    vector<int> p,q;

                    for(m=;m<n;m++)

                    {

                         if(m<i||m>j) p.pb(a[m]);//p剩余区间

                         else q.pb(a[m]);//q选定区间

                    }

                    sort(p.rbegin(),p.rend());//rbegin反向迭代器

                    for(m=;m<k&&m<p.size();m++)

                         q.pb(p[m]);

                    sort(q.rbegin(),q.rend());

                    int sum=;

                    for(m=;m<=j-i;m++) sum+=q[m];

                    if(sum>mx) mx=sum;

               }

          }

          pf("%d\n",mx);

     }

}

CodeForces 363D

这题其实是二分法。需要买最多的车，判断能不能买k辆车的话，一定是钱最多的k个人，买最便宜的k辆车，然后二分查找找出最大k

第二条件即花钱最少其实可以算出来，最关键还是k的大小

#include <iostream>

#include <string>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <cctype>

#include <vector>

#include <iterator>

#include <set>

#include <map>

#include <sstream>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))

#define pf printf

#define sf scanf

#define spf sprintf

#define pb push_back

#define debug printf("!\n")

#define INF 10000

#define MAXN 5010

#define MAX(a,b) a>b?a:b

#define blank pf("\n")

#define LL long long

#define ALL(x) x.begin(),x.end()

#define INS(x) inserter(x,x.begin())

#define pqueue priority_queue

int b[],p[];

int n,m,a;

bool ok(int k)

{

     int aa = a;

     int d=n-k;

     for(int i=;i<k;i++)

     {

          if(b[i+d]<p[i])

               aa-=(p[i]-b[i+d]);

          if(aa<) return false;

     }

     return true;

}

int main()

{

     int i,j;

     while(sf("%d%d%d",&n,&m,&a)==)

     {

          for(i=;i<n;i++) sf("%d",&b[i]);

          for(i=;i<m;i++) sf("%d",&p[i]);

          sort(b,b+n);

          sort(p,p+m);

          int l=,r=min(n,m),mid;

          while(l<=r)

          {

               mid = (l+r)>>;

               if(ok(mid)) l=mid+;

               else r=mid-;

          }

          int s =;

          for(i=;i<l-;i++)

               s+=p[i];

          pf("%d %d\n",l-,s-a);

     }

}