贪心

环形均分纸牌问题

image-20240512023309519

image-20240512023337062

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define LL long long

LL read(){ 
    LL s=0,ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()) s=((s<<1)+(s<<3))+c-'0';
    return s*ne;
}

const int CN=1e6+6;

LL n,x1,a[CN],c[CN],_a,rec[CN];
LL llabs(LL a) {return a>0 ? a:-a;}

int main()
{
    n=read();
    LL sigma = 0;
    for(int i=1;i<=n;i++) 
        a[i] = read(),sigma += a[i];
    _a = sigma/n; //求平均值 
    
    rec[0] = c[0] = 0;    
    for(int i=1;i<=n;i++)
        rec[i] = c[i] = c[i-1]+a[i]-_a; //递推c[i]
            
    sort(c+1,c+n+1);
    x1 = c[(n+1)/2]; //计算中位数
        
    LL ans=0;
    for(int i=1;i<=n;i++)
        ans += llabs(x1-c[i]); //求代价
    printf("%lld\n",ans);
    for(int i=1;i<n;i++)
        printf("%lld %lld\n",x1-rec[i-1],-(x1-rec[i])); //输出搬运数
    printf("%lld %lld",x1-rec[n-1],-x1); //处理环
    
    return 0;
}

反悔贪心

img

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int N=300005;
int n,p[N];
long long ans;
priority_queue<int,vector<int>
                  ,greater<int> > q;

int main(){
  cin>>n;
  for(int i=1; i<=n; i++) cin>>p[i];
  
  for(int i=1; i<=n; i++){
    if(!q.empty()&&q.top()<p[i]){
      ans+=(p[i]-q.top()); 
      q.pop();      //卖出pt
      q.push(p[i]); //买入pi (为了反悔)
    }
    q.push(p[i]);   //买入pi (为了交易)
  }
  cout<<ans<<endl;
  return 0;
}

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

struct node{
    int d,p;
    bool operator<(node &b){
      return d<b.d;
    }
}w[100005];
long long ans;
priority_queue<int,vector<int>
                ,greater<int> > q;

int main(){
  int n; scanf("%d",&n);
  for(int i=1; i<=n; i++)
  scanf("%d%d",&w[i].d,&w[i].p);
  sort(w+1,w+n+1); //按截止时间排序
  
  for(int i=1; i<=n; i++){
    if(w[i].d==q.size()){ //截止时间相同
      if(w[i].p>q.top()){ //利润更大
        ans-=q.top();   //反悔
        q.pop();
        q.push(w[i].p);
        ans+=w[i].p;    //贪心
      }
    }
    else{ //截止时间大
      q.push(w[i].p);
      ans+=w[i].p;    //贪心
    }
  }
  printf("%lld",ans);
  return 0;
}