题解 P6531 【[COCI2015-2016#1] BALONI】

KadiaNEFU · 2020-05-06 12:48:34 · 题解

咋一看还以为就是个递减贪心，看了样例发现不对，是一排气球，从左向右射箭，每击中一个气球箭的高度会下降1，但箭始终是从左向右移动的。

思路：用一个map记录key的高度的箭有多少只。

• 如果输入的a[i]的value值大于0，说明这个高度有箭，这个value--，a[i]-1的value再++，因为这只箭射中这个气球后高度会减1，那么a[i]-1高度的箭的数量就会加1。

• 如果输入的a[i]的value值为0，说明这个高度没有箭，所以就要我们往这个高度射一只箭，sum++(sum记录射了多少只箭)，然后射中后同样下降一个高度，那么a[i]-1高度的箭的数量就会加1。

  
  #include<bits/stdc++.h>
  using namespace std;
  int a[1000005];
  int main()
  {
  int n;
  cin >> n;
  map<int,int>save;
  int sum=0;
  for(int i=1;i<=n;i++)
  {
      cin >> a[i];
      if(save[a[i]]>0)
      {
          save[a[i]]--;
          save[a[i]-1]++;
      }
      else
      {
          sum++;
          save[a[i]-1]++;
      }
  }
  cout << sum << endl ;
  return 0;
  }