Eugeny and Play List - CodeForces 302B - Virtual Judge (csgrandeur.cn)

题意:给定歌曲和播放时间和播放次数，找出一分钟播放歌曲

加深对二分的理解

code1:双指针

#include<bits/stdc  .h> using namespace std; const int N=1e5 10; typedef long long LL; struct node {  LL x,y; }a[N]; LL q[N]; int n,m;  void solve() {  LL sum=0;  int cnt=1;  for(int i=1;i<=n;i  )  {   sum =a[i].x*a[i].y;      while(q[cnt]<=sum)   {    cout<<i<<endl;    cnt  ;    if(cnt>m) return;   }     }  }   int main() {  cin>>n>>m;    for(int i=1;i<=n;i  ) cin>>a[i].x>>a[i].y;    for(int i=1;i<=m;i  ) cin>>q[i];    solve();     return 0; }

code2:二分 前缀和

#include<bits/stdc  .h> #define x first #define y second #define mak make_pair #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define debug(a) cout<<a<<'\n' #define endl '\n' #define umap unordered_map using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII; const int N=1e5 10,M=1,inf=0x3f3f3f3f,mod=1e9 7; LL s[N]; int n,m; void solve(int x) {  int l=1,r=n;    while(l<r)  {   int mid=l r>>1;   if(s[mid]>=x) r=mid;   else l=mid 1;  }  cout<<l<<endl; }  int main() {  IOS;  LL x,y;  cin>>n>>m;    for(int i=1;i<=n;i  )  {   cin>>x>>y;   s[i]=s[i-1] x*y;  }    while(m--)  {   cin>>x;   solve(x);  }      return 0; }  

END

---